题意：
求两个串的最大连续子串
一个串建SAM，另一个串在上面跑
注意如果走了Suffix Link，sum需要更新为t[u].val+1
Suffix Link有点像失配吧，当前状态s走不了了就到Suffix Link指向的状态fa上去，fa是s的后缀所以是可行的，并且有更多走的机会
#include#include #include #include using namespace std;const int N=25e4+5;int n,m;char a[N],b[N];struct State{ int ch[26],par,val; State():par(0),val(0){memset(ch,0,sizeof(ch));}}t[N<<1];int sz,root,last;inline int nw(int _){t[++sz].val=_;return sz;}void iniSAM(){sz=0;root=last=nw(0);}void extend(int c){ int p=last,np=nw(t[p].val+1); while(p&&t[p].ch[c]==0) t[p].ch[c]=np,p=t[p].par; if(p==0) t[np].par=root; else{ int q=t[p].ch[c]; if(t[q].val==t[p].val+1) t[np].par=q; else{ int nq=nw(t[p].val+1); memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch)); t[nq].par=t[q].par; t[q].par=t[np].par=nq; while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].par; } } last=np;}int ans;void solve(){ iniSAM(); for(int i=1;i<=n;i++) extend(a[i]-'a'); int sum=0,u=root; for(int i=1;i<=m;i++){ //printf("hi %d %c \n",i,b[i]); int c=b[i]-'a'; if(t[u].ch[c]) u=t[u].ch[c],ans=max(ans,++sum);//puts("ha"); else{ while(u&&!t[u].ch[c]) u=t[u].par; if(!u) u=root,sum=0;//puts("Not Found"); else sum=t[u].val+1,u=t[u].ch[c],ans=max(ans,sum);//puts("Find"); } //printf("u %d %d\n",u,sum); } printf("%d",ans);}int main(){ freopen("in","r",stdin); scanf("%s%s",a+1,b+1); n=strlen(a+1);m=strlen(b+1); solve();}