3160 最长公共子串

 

 时间限制: 2 s

 空间限制: 128000 KB

 题目等级 : 大师 Master

 

 

 

题目描述 

Description

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

输入描述 

Input Description

读入两个字符串

输出描述 

Output Description

输出最长公共子串的长度

样例输入 

Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother

样例输出 

Sample Output

27

数据范围及提示 

Data Size & Hint

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

分类标签 Tags 

 

   

模板题：

#include
          
           #include
           
            #include
            
             using namespace std;const int N=2e5+10;int n,c[N],h[N],sa[N],tsa[N],rank[N],trank[N];char s[N];struct Suffix{    void DA(int maxx=256){        int p;        for(int i=0;i<=maxx;i++) c[i]=0;        for(int i=1;i<=n;i++) c[rank[i]=s[i]]++;        for(int i=2;i<=maxx;i++) c[i]+=c[i-1];        for(int i=n;i;i--) sa[c[rank[i]]--]=i;        trank[sa[1]]=p=1;        for(int i=2;i<=n;i++){            if(rank[sa[i]]!=rank[sa[i-1]]) p++;            trank[sa[i]]=p;        }        for(int i=1;i<=n;i++) rank[i]=trank[i];        for(int k=1;p
             
              <<=1,maxx=p){            p=0;            for(int i=n-k+1;i<=n;i++) tsa[++p]=i;            for(int i=1;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;            for(int i=0;i<=maxx;i++) c[i]=0;            for(int i=1;i<=n;i++) trank[i]=rank[tsa[i]];            for(int i=1;i<=n;i++) c[trank[i]]++;            for(int i=2;i<=maxx;i++) c[i]+=c[i-1];            for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i];            trank[sa[1]]=p=1;            for(int i=2;i<=n;i++){                if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++;                trank[sa[i]]=p;            }            for(int i=1;i<=n;i++) rank[i]=trank[i];        }        for(int i=1,k=0;i<=n;i++){            int j=sa[rank[i]-1];            while(s[i+k]==s[j+k]) k++;            h[rank[i]]=k;if(k>0) k--;        }    }    void work(){        scanf("%s",s+1);n=strlen(s+1);        s[++n]='#';int T=n;        scanf("%s",s+n+1);int t=strlen(s+n+1);        n+=t;        DA();        //min(两个Suffix的lcp){Suffix不包含'#'}         int ans(0);        for(int i=1;i<=n;i++){            if(ans
              
               T&&sa[i-1]
               
                T) ans=h[i]; } } printf("%d\n",ans); }}suffix;int main(){ suffix.work(); return 0;}