【BZOJ2946】[Poi2000]公共串 后缀数组+二分

时间：2023-11-11 19:42:50

【BZOJ2946】[Poi2000]公共串

Description

       给出几个由小写字母构成的单词，求它们最长的公共子串的长度。
任务：
l        读入单词
l        计算最长公共子串的长度
l        输出结果

Input

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

Output

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

Sample Input

3
abcb
bca
acbc

Sample Output

２

题解：把所有字符串连起来，中间用极小值隔开（极小值不能相同，用最大值也行），跑后缀数组，然后二分答案，如果能找出一段区间包括所有的单词，并且公共线坠长度≥答案，则答案可行

感觉几年没写后缀数组了，细节多得可以~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

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<n;i++)	st[x[i]=r[i]]++;

	for(i=1;i<m;i++)	st[i]+=st[i-1];

	for(i=n-1;i>=0;i--)	sa[--st[x[i]]]=i;

	for(j=p=1;p<n;j<<=1,m=p)

	{

		for(i=n-j,p=0;i<n;i++)	y[p++]=i;

		for(i=0;i<n;i++)	if(sa[i]>=j)	y[p++]=sa[i]-j;

		for(i=0;i<m;i++)	st[i]=0;

		for(i=0;i<n;i++)	st[x[y[i]]]++;

		for(i=1;i<m;i++)	st[i]+=st[i-1];

		for(i=n-1;i>=0;i--)	sa[--st[x[y[i]]]]=y[i];

		for(swap(x,y),i=p=1,x[sa[0]]=0;i<n;i++)

			x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;

	}

	for(i=1;i<n;i++)	rank[sa[i]]=i;

	for(i=k=0;i<n-1;h[rank[i++]]=k)

		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

}

int check(int sta)

{

	memset(s,0,sizeof(s));

	int i,sum=0,l=0;

	s[bel[sa[0]]]++,sum+=(s[bel[sa[0]]]==1);

	for(i=1;i<n;i++)

	{

		s[bel[sa[i]]]++,sum+=(s[bel[sa[i]]]==1);

		if(h[i]<sta)	for(;l<i;l++)	s[bel[sa[l]]]--,sum-=(s[bel[sa[l]]]==0);

		else if(sum==num)	return 1;

	}

	return 0;

}

int main()

{

	scanf("%d",&num);

	int i,j,a;

	for(i=1;i<=num;i++)

	{

		scanf("%s",str);

		a=strlen(str);

		for(j=0;j<a;j++)	bel[n]=i,r[n++]=str[j]-'a'+num;

		n++;

	}

	for(i=0;i<n;i++)	if(!bel[i])	r[i]=bel[i-1]-1;

	m=26+num;

	work();

	int L=1,R=n/num,mid;

	while(L<R)

	{

		mid=L+R>>1;

		if(check(mid))	L=mid+1;

		else	R=mid;

	}

	printf("%d\n",L-1);

	return 0;

}

相关文章