codevs 3160 最长公共子串（SAM）

3160 最长公共子串

 

题目描述 Description

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

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入 Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother

样例输出 Sample Output

27

数据范围及提示 Data Size & Hint

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

【思路】

　　SAM求LCS

【代码】

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N = *1e5+;

 char s[N];

 int sz,root,last,fa[N],ch[N][],l[N],n;

 void add(int x) {

     int c=s[x]-'a';

     int p=last,np=++sz; last=np;

     l[np]=x+;

     for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;

     if(!p) fa[np]=root;

     else {

         int q=ch[p][c];

         if(l[p]+==l[q]) fa[np]=q;

         else {

             int nq=++sz; l[nq]=l[p]+;

             memcpy(ch[nq],ch[q],sizeof(ch[q]));

             fa[nq]=fa[q];

             fa[np]=fa[q]=nq;

             for(;p&&q==ch[p][c];p=fa[p]) ch[p][c]=nq;

         }

     }

 }

 void build() {

     root=last=++sz;

     scanf("%s",s);

     n=strlen(s);

     for(int i=;i<n;i++) add(i);

 }

 void lcs() {

     scanf("%s",s);

     n=strlen(s);

     int p=root,ans=,len=;

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

         int c=s[i]-'a';

         if(ch[p][c]) { len++; p=ch[p][c]; }

         else {

             for(;p&&!ch[p][c];p=fa[p]);

             if(!p) { p=root; len=; }

             else {

                 len=l[p]+; p=ch[p][c];

             }

         }

         if(len>ans) ans=len;

     }

     printf("%d",ans);

 }

 int main() {

     build();

     lcs();

     return ;

 }