给出几个由小写字母构成的单词，求它们最长的公共子串的长度。
任务
- 从文件中读入单词
- 计算最长公共子串的长度
- 输出结果到文件
输入
文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。
输出：
仅一行，一个整数，最长公共子串的长度。
样例输入：
3 abcb bca acbc
样例输出：
2
题解：
显然所有的串先合并，然后用不同符号间隔
最后二分答案，找到high[i]大于答案x的 并不断往后扩展 如果满足所有子串都覆盖到即满足
为什么我总喜欢把 L开成char?
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 const int N=20005; 9 int s[N],n=0,k,tmp[N],sa[N],rk[N],high[N],color[N],m,l[6];char S[6][2005]; 10 bool comp(int i,int j){ 11 if(rk[i]!=rk[j])return rk[i]<rk[j]; 12 int ri=i+k<=n?rk[i+k]:-1; 13 int rj=j+k<=n?rk[j+k]:-1; 14 return ri<rj; 15 } 16 void Getsa(){ 17 for(int i=1;i<=n;i++){ 18 sa[i]=i;rk[i]=s[i]; 19 } 20 for(k=1;k<=n;k<<=1){ 21 sort(sa+1,sa+n+1,comp); 22 for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]); 23 for(int i=1;i<=n;i++)rk[i]=tmp[i]; 24 } 25 } 26 void Gethight(){ 27 int j,h=0; 28 for(int i=1;i<=n;i++){ 29 j=sa[rk[i]-1]; 30 if(h)h--; 31 for(;j+h<=n && i+h<=n;h++)if(s[i+h]!=s[j+h])break; 32 high[rk[i]-1]=h; 33 } 34 } 35 void prework(int m){ 36 int p=0; 37 for(int i=1;i<=m;i++){ 38 for(int j=1;j<=l[i];j++) 39 p++,color[p]=i; 40 p++; 41 } 42 } 43 bool d[8]; 44 bool check(int lim){ 45 int p,ret; 46 for(int i=1;i<n;i++){ 47 if(high[i]>=lim){ 48 p=i; 49 while(p<n && high[p+1]>=lim)p++;p++; 50 for(int j=1;j<=m;j++)d[j]=false; 51 for(int j=i;j<=p;j++)d[color[sa[j]]]=true; 52 ret=p;p=1; 53 while(p<=m && d[p])p++; 54 if(p==m+1)return true; 55 i=ret; 56 } 57 } 58 return false; 59 } 60 int main() 61 { 62 freopen("pow.in","r",stdin); 63 freopen("pow.out","w",stdout); 64 int r=2e8; 65 scanf("%d",&m); 66 for(int i=1;i<=m;i++){ 67 scanf("%s",S[i]); 68 l[i]=strlen(S[i]); 69 if(l[i]<r)r=l[i]; 70 for(int j=0;j<l[i];j++)s[++n]=S[i][j]; 71 s[++n]=i; 72 } 73 Getsa();Gethight();prework(m); 74 int l=0,mid,ans; 75 while(l<=r){ 76 mid=(l+r)>>1; 77 if(check(mid))ans=mid,l=mid+1; 78 else r=mid-1; 79 } 80 printf("%d ",ans); 81 return 0; 82 }