【题意】给定两个字符串S和T，求最长公共子串。len<=10^5。

【算法】后缀自动机

【题解】对字符串S建SAM，然后令串T在S上跑匹配。

这是自动机最原本的功能——匹配，就是串T在SAM(S)上走，不能匹配就沿失配边走，这样得到的是T上以每个字符结尾的子串中与S的最长公共子串，取Max即是答案。

注意失配不要走到0节点处。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=100010;struct tree{
    int len,fa,t[30];}t[maxn*2];int last,n,m,tot;char s[maxn],T[maxn];void insert(int c){    int np=++tot;    t[np].len=t[last].len+1;    int x=last;    while(x&&!t[x].t[c])t[x].t[c]=np,x=t[x].fa;    last=np;    if(!x)t[np].fa=1;else{        int y=t[x].t[c];        if(t[y].len==t[x].len+1)t[np].fa=y;else{            int nq=++tot;            t[nq]=t[y];            t[nq].len=t[x].len+1;            t[nq].fa=t[y].fa;t[np].fa=t[y].fa=nq;            while(x&&t[x].t[c]==y)t[x].t[c]=nq,x=t[x].fa;        }    }}int main(){    scanf("%s",T+1);m=strlen(T+1);    last=tot=1;    for(int i=1;i<=m;i++)insert(T[i]-'a');    scanf("%s",s+1);n=strlen(s+1);    int ans=0,cnt=0,now=1;    for(int i=1;i<=n;i++){        while(now!=1&&!t[now].t[s[i]-'a'])now=t[now].fa,cnt=t[now].len;        if(t[now].t[s[i]-'a'])cnt++,now=t[now].t[s[i]-'a'];else cnt=0;        ans=max(ans,cnt);    }    printf("%d",ans);    return 0;}