经典题
注意匹配的时候：用t串去s串的SAM里进行匹配，和字典树一样遍历t中字符，用cur记录当前已经匹配的长度，如果能当前字符能匹配则cur++(这里不能直接用cur=len[now]),反之用link指针进行失配，直到完成匹配后cur=len[now]
为什么匹配成功时不能直接cur=len[now]?因为自动机上的转移是在后面加一个字符，但是不保证前面不加字符，因为每个结点的len是该节点代表的maxlen
但是失配后再转移成功则可以用cur=len[now],因为失配结点代表的最短串长度都有len[now]+1，即到了这个状态，那么t串一定有minlen[now]的长度,所以其link指向的状态的maxlen[now]=minlen[now-1]一定是满足条件的！
#include<bits/stdc++.h> using namespace std; #define maxn 250005 struct SAM{ int cnt,last; int nxt[maxn<<1][26]; int link[maxn<<1]; int len[maxn<<1]; SAM(){ cnt=last=1; } void insert(int c){ int p=last,np=last=++cnt; len[np]=len[p]+1; for(;p&&!nxt[p][c];p=link[p]) nxt[p][c]=np; if(!p){link[np]=1;return;} int q=nxt[p][c]; if(len[q]==len[p]+1){link[np]=q;return;} int clone=++cnt; link[clone]=link[q]; len[clone]=len[p]+1; memcpy(nxt[clone],nxt[q],sizeof nxt[q]); link[q]=link[np]=clone; for(;p&&nxt[p][c]==q;p=link[p]) nxt[p][c]=clone; } int query(char *s){ int now=1,Len=strlen(s),cur=0,Max=0; for(int i=0;i<Len;i++){ int c=s[i]-‘a‘; if(nxt[now][c]){ now=nxt[now][c]; cur++; } else { while(now && !nxt[now][c])now=link[now]; if(now){ cur=len[now]+1; now=nxt[now][c]; } else { now=1; cur=0; } } Max=max(Max,cur); } return Max; } }p; char s[maxn],t[maxn]; int main(){ scanf("%s%s",s,t); int len1=strlen(s); int len2=strlen(t); for(int i=0;i<len1;i++) p.insert(s[i]-‘a‘); cout<<p.query(t)<<endl; }
原文：https://www.cnblogs.com/zsben991126/p/11314564.html