poj2774，codevs3160

题目描述 Description

给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入 Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother

样例输出 Sample Output

27

数据范围及提示 Data Size & Hint

单个字符串的长度不超过100000

 

错误代码

1         else{2             while(now&&!c[now][s2[i]-'a'])now=f[now],qwq;3                 if(c[now][s2[i]-'a']){4                 now=c[now][s2[i]-'a'];len=l[now]+1;if(len>ans)ans=len;5             }6         7         }

一定要判断now是否跳到了0，否则妥妥地死循环

1 #include
     
       2 #include
      
        3 const int N=200005; 4 #define qwq puts("*") 5 char s1[N>>1],s2[N>>1]; 6 int pre=1,cnt=1,f[N],l[N],l1,l2,c[N][27],ans; 7  8 inline void ins(int x){ 9     int p=pre,np=++cnt;pre=np;l[np]=l[p]+1;10     for(;p&&!c[p][x];p=f[p])c[p][x]=np;11     if(!p)f[np]=1;12     else{13         int q=c[p][x];14         if(l[q]==l[p]+1)f[np]=q;15         else{16             int nq=++cnt;17             memcpy(c[nq],c[q],sizeof(c[q]));18             f[nq]=f[q];l[nq]=l[p]+1;19             f[q]=f[np]=nq;20             for(;c[p][x]==q;p=f[p])c[p][x]=nq;21         }22     }    23 }24 int main(){25     scanf("%s%s",s1,s2);26     l1=strlen(s1);l2=strlen(s2);//printf("%d %d\n",l1,l2);27     for(int i=0;i
       
        ans)ans=len;39     }40     printf("%d",ans);41     return 0;42 }