[POI2000] 最长公共子串

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务

从文件中读入单词
计算最长公共子串的长度
输出结果到文件

输入

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

输出：

仅一行，一个整数，最长公共子串的长度。

样例输入：

3

abcb

bca

acbc

样例输出：

2

题解：
显然所有的串先合并，然后用不同符号间隔
最后二分答案，找到high[i]大于答案x的 并不断往后扩展 如果满足所有子串都覆盖到即满足
为什么我总喜欢把 L开成char?

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int N=;

 int s[N],n=,k,tmp[N],sa[N],rk[N],high[N],color[N],m,l[];char S[][];

 bool comp(int i,int j){

     if(rk[i]!=rk[j])return rk[i]<rk[j];

     int ri=i+k<=n?rk[i+k]:-;

     int rj=j+k<=n?rk[j+k]:-;

     return ri<rj;

 }

 void Getsa(){

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

         sa[i]=i;rk[i]=s[i];

     }

     for(k=;k<=n;k<<=){

         sort(sa+,sa+n+,comp);

         for(int i=;i<=n;i++)tmp[sa[i]]=tmp[sa[i-]]+comp(sa[i-],sa[i]);

         for(int i=;i<=n;i++)rk[i]=tmp[i];

     }

 }

 void Gethight(){

     int j,h=;

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

         j=sa[rk[i]-];

         if(h)h--;

         for(;j+h<=n && i+h<=n;h++)if(s[i+h]!=s[j+h])break;

         high[rk[i]-]=h;

     }

 }

 void prework(int m){

     int p=;

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

         for(int j=;j<=l[i];j++)

             p++,color[p]=i;

         p++;

     }

 }

 bool d[];

 bool check(int lim){

     int p,ret;

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

         if(high[i]>=lim){

             p=i;

             while(p<n && high[p+]>=lim)p++;p++;

             for(int j=;j<=m;j++)d[j]=false;

             for(int j=i;j<=p;j++)d[color[sa[j]]]=true;

             ret=p;p=;

             while(p<=m && d[p])p++;

             if(p==m+)return true;

             i=ret;

         }

     }

     return false;

 }

 int main()

 {

     freopen("pow.in","r",stdin);

     freopen("pow.out","w",stdout);

     int r=2e8;

     scanf("%d",&m);

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

         scanf("%s",S[i]);

         l[i]=strlen(S[i]);

         if(l[i]<r)r=l[i];

         for(int j=;j<l[i];j++)s[++n]=S[i][j];

         s[++n]=i;

     }

     Getsa();Gethight();prework(m);

     int l=,mid,ans;

     while(l<=r){

         mid=(l+r)>>;

         if(check(mid))ans=mid,l=mid+;

         else r=mid-;

     }

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

     return ;

 }

巴特西

[POI2000] 最长公共子串

最新文章

热门文章