【BZOJ2946】[Poi2000]公共串
Description
给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
l 读入单词
l 计算最长公共子串的长度
l 输出结果
Input
文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。
Output
仅一行,一个整数,最长公共子串的长度。
Sample Input
3 abcb bca acbc
Sample Output
2
题解:把所有字符串连起来,中间用极小值隔开(极小值不能相同,用最大值也行),跑后缀数组,然后二分答案,如果能找出一段区间包括所有的单词,并且公共线坠长度≥答案,则答案可行
感觉几年没写后缀数组了,细节多得可以~
#include#include #include #include using namespace std;int n,m,num;const int maxn=10100;int r[maxn],ra[maxn],rb[maxn],sa[maxn],sb[maxn],st[maxn],rank[maxn],h[maxn],s[10],bel[maxn];char str[maxn];void work(){ int i,j,k,*x=ra,*y=rb,p; for(i=0;i =0;i--) sa[--st[x[i]]]=i; for(j=p=1;p <<=1,m=p) { for(i=n-j,p=0;i =j) y[p++]=sa[i]-j; for(i=0;i =0;i--) sa[--st[x[y[i]]]]=y[i]; for(swap(x,y),i=p=1,x[sa[0]]=0;i >1; if(check(mid)) L=mid+1; else R=mid; } printf("%d\n",L-1); return 0;}