[SPOJ1811]Longest Common Substring 后缀自动机 最长公共子串
题目链接：http://www.spoj.com/problems/LCS/
题意如题目，求两个串的最大公共子串LCS。
首先对其中一个字符串A建立SAM，然后用另一个字符串B在上面跑。
用一个变量Lcs来记录当前答案，如果能转移到下一个状态则Lcs++。
若不能转移说明需要重新选择状态，则不断地跳到当前状态的fa状态，如果发现能够转移就停下来，Lcs变为当前状态的len+1并转移到下一个可行状态。
这里很像AC自动机的fail指针的跳跃。因为fa状态是当前状态的后缀，已经被匹配过，而fa状态有更多的机会转移。
于是最后的答案就是所有状态下Lcs的最大值。这样做的总体思想是求出对于每一个位置能向前扩展的最大长度。值得注意的是对于一个成功匹配状态s的匹配长度显然也可以作为它fa的匹配长度。因为fa的right集合一定包含了s的right集合，即都包含了当前的Lcs串的结束位置，从s开始向上更新一遍就好了，不过这里好像不需要。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,m; 6 char a[250010],b[250010]; 7 struct State{ 8 int ch[26],fa,len; 9 void init(){ 10 fa=-1; 11 len=0; 12 memset(ch,-1,sizeof(ch)); 13 } 14 }T[500010]; 15 int cnt=0,la; 16 void Extend(int c){ 17 int end=++cnt,tmp=la; 18 T[end].init(); 19 T[end].len=T[tmp].len+1; 20 while((~tmp)&&(!~T[tmp].ch[c])){ 21 T[tmp].ch[c]=end; 22 tmp=T[tmp].fa; 23 } 24 if(!~tmp) T[end].fa=0; 25 else{ 26 int ne=T[tmp].ch[c]; 27 if(T[tmp].len+1==T[ne].len) T[end].fa=ne; 28 else{ 29 int np=++cnt; 30 T[np]=T[ne]; 31 T[np].len=T[tmp].len+1; 32 T[end].fa=T[ne].fa=np; 33 while((~tmp)&&T[tmp].ch[c]==ne){ 34 T[tmp].ch[c]=np; 35 tmp=T[tmp].fa; 36 } 37 } 38 } 39 la=end; 40 } 41 void solve(){ 42 int ans=0; 43 T[0].init(); 44 for(int i=1;i<=n;i++) Extend(a[i]-'a'); 45 int Lcs=0,o=0; 46 for(int i=1;i<=m;i++){ 47 int c=b[i]-'a'; 48 if(~T[o].ch[c]){ 49 o=T[o].ch[c]; 50 ans=max(ans,++Lcs); 51 } 52 else{ 53 while((~o)&&(!~T[o].ch[c])) o=T[o].fa; 54 if(!~o) o=Lcs=0; 55 else{ 56 Lcs=T[o].len+1; 57 o=T[o].ch[c]; 58 ans=max(ans,Lcs); 59 } 60 } 61 } 62 printf("%d ",ans); 63 } 64 int main(){ 65 scanf("%s%s",a+1,b+1); 66 n=strlen(a+1); 67 m=strlen(b+1); 68 solve(); 69 return 0; 70 }