Description
给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
读入单词
计算最长公共子串的长度
输出结果
Input
文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。
Output
仅一行,一个整数,最长公共子串的长度。
Sample Input
3
abcb
bca
acbc
Sample Output
2
/**************************************************************
Problem: 2946
User: ictsing
Language: C++
Result: Accepted
Time:40 ms
Memory:1444 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int mt = 2000+5 ;
char s[5][mt];
ull p[mt],f[5][mt],h[mt],hsh[mt],mark[mt];
ull bas=131;
int n;
int cnt,top;
int len[5];
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int find(ull x)
{
int l=1,r=cnt;
while(l<=r)
{
int mid=(l+r)>>1;
if(hsh[mid]==x) return mid;
if(hsh[mid]>x) r=mid-1;
else l=mid+1;
}
return 0;
}
bool judge(int x)
{
cnt=0,top=0;
for(int i=0;i+x<=len[0];i++)
h[++top]=f[0][i+x]-f[0][i]*p[x];
sort(h+1,h+top+1);
for(int i=1;i<=top;i++)
if(h[i]!=h[i-1]) hsh[++cnt]=h[i];
memset(mark,0,sizeof(mark));
for(int i=1;i<n;i++)
for(int j=0;j+x<=len[i];j++)
{
ull pp=f[i][j+x]-f[i][j]*p[x];
int x=find(pp);
if(x!=0&&mark[x]==i-1) mark[x]=i;
}
for(int i=1;i<=cnt;i++)
if(mark[i]==n-1) return 1;
return 0;
}
int main()
{
p[0]=1;
for(int i=1;i<=2000;i++) p[i]=p[i-1]*bas;
n=read();
int lft=0,rgt=2000,ans=0;
for(int i=0;i<n;i++)
{
scanf("%s",s[i]+1);
len[i]=strlen(s[i]+1);
f[i][0]=0;
for(int j=1;j<=len[i];j++)
f[i][j]=f[i][j-1]*bas+s[i][j];
rgt=min(rgt,len[i]);
}
while(lft<=rgt)
{
int mid=(lft+rgt)>>1;
if(judge(mid)) ans=mid,lft=mid+1;
else rgt=mid-1;
}
printf("%d\n",ans);
return 0;
}
评论