Chrysanthemum's Blog

题意：给你n个字符串，求最长的字符串使得它是至少n/2+1个字符串的子串，输出所有这样的字符串。

首先我们把n个字符串全部连起来，中间用分隔符连起来。二分答案，然后对于每一组大于等于mid的height，只要判断是否存在于大于n/2个字符串中。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
int n,len,l,num;
int wa[100100],wb[100100],ws[100100],wv[100100],sa[100100],r[100100],rank[100100],height[100100],flag[110],id[100100],ans[100100];
char s[1010];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];} 
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for (i=0;i<m;i++) ws[i]=0;
	for (i=0;i<n;i++) ws[x[i]=r[i]]++;
	for (i=1;i<m;i++) ws[i]+=ws[i-1];
	for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
	for (j=1,p=1;p<n;j*=2,m=p)
	{
		p=0;
		for (i=n-j;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<n;i++) wv[i]=x[y[i]];
		for (i=0;i<m;i++) ws[i]=0;
		for (i=0;i<n;i++) ws[wv[i]]++;
		for (i=1;i<m;i++) ws[i]+=ws[i-1];
		for (i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
		for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for (i=1;i<=n;i++) rank[sa[i]]=i;
	for (i=0;i<n;height[rank[i++]]=k)
		for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
int check(int mid)
{
	int isok=0,j;
	for (int i=1;i<=len;i=j+1)
	{
		for (;height[i]<mid&&i<=len;i++);
		for (j=i;height[j]>=mid;j++)
		if (j-i+1<n/2+1) continue;
		memset(flag,0,sizeof(flag));
		int tot=0;
		for (int k=i-1;k<j;k++)
			if (!flag[id[sa[k]]]){flag[id[sa[k]]]=1;tot++;}
		if (tot>=n/2+1)
		{
			if (!isok){isok=1;num=0;}
			ans[++num]=sa[i];
		}
	}
	return isok;
}
int main()
{
	scanf("%d",&n);
	while (n)
	{
		len=0;num=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%s",s);
			l=strlen(s);
			for (int j=0;j<l;j++) {r[len+j]=s[j]+100;id[len+j]=i;}
			r[len+l]=i;
			id[len+l]=0;
			len+=l+1;
		}
		len--;r[len]=0;
		da(r,sa,len+1,280);
		calheight(r,sa,len);
		height[len+1]=-1;
		int L=0,R=1000;
		while (L<R)
		{
			int mid=((L+R)>>1)+1;
			if (check(mid)) L=mid;else R=mid-1;
		}
		if (!R)printf("?\n");else
		{
			for (int i=1;i<=num;i++)
			{
				int k=ans[i];
				for (int j=0;j<R;j++) printf("%c",r[k+j]-100);
				printf("\n");
			}
		}
		scanf("%d",&n);
		if (n) printf("\n");
	}
}