codevs 3160 最长公共子串 后缀自动机

http://codevs.cn/problem/3160/

后缀自动机板子题，匹配的时候要注意如果到一个点失配向前匹配到一个点时，此时的tmp（当前匹配值）为t[j].len+1而不是t[t[j].sig[z]].len，想一下自动机的特质就可以明白了。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<map>

 using namespace std;

 const int maxn=;

 char ch1[maxn]={},ch2[maxn]={};

 int siz1,siz2;

 struct nod{

     int sig[];

     int f,len;

 }t[maxn*];int tot=,la=;

 void add(int z){

     int x=++tot;int i=la;

     t[x].len=t[la].len+;

     for(;i&&!t[i].sig[z];i=t[i].f)

         t[i].sig[z]=x;

     if(!i)t[x].f=;

     else{

         int p=t[i].sig[z];

         if(t[p].len==t[i].len+)t[x].f=p;

         else{

             int y=++tot;

             t[y]=t[p];t[y].len=t[i].len+;

             t[x].f=t[p].f=y;

             for(;i&&t[i].sig[z]==p;i=t[i].f){

                 t[i].sig[z]=y;

             }

         }

     }

     la=x;

 }

 int main(){

     memset(t,,sizeof(t));

     scanf("%s",ch1+);

     scanf("%s",ch2+);

     siz1=strlen(ch1+);

     siz2=strlen(ch2+);

     for(int i=;i<=siz1;i++)add(int(ch1[i]-'a'));

     int ans=,j=,tmp=;

     for(int i=;i<=siz2;i++){

         int z=ch2[i]-'a';

         if(t[j].sig[z]){j=t[j].sig[z];tmp++;}

         else{

             while(j&&!t[j].sig[z])

                 j=t[j].f;

             if(!j){j=;tmp=;}

             else {tmp=t[j].len+;j=t[j].sig[z];}

         }

         if(tmp>ans)ans=tmp;

     }printf("%d\n",ans);

     return ;

 }