记录编号	413722	评测结果	AAAAAAAAAA
题目名称	[POJ3294]生命形态	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.059 s
提交时间	2017-06-12 13:14:26	内存使用	11.24 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N=201000;
char str[N];int s[N];
int n,m,p,r[N],sa[N],h[N],Wa[N],Wb[N],Ws[N];
bool cmp(int *r,int x,int y,int l){
	return r[x]==r[y]&&r[x+l]==r[y+l];
}
bitset<110> S[N];
void getsa(){
	int m=1000,i,j,k,*x=Wa,*y=Wb;
	for (i=1;i<=n+n;i++) x[i]=y[i]=0;
	for (i=0;i<=m;i++) Ws[i]=0;
	for (i=1;i<=n;i++) Ws[x[i]=s[i]]++;
	for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
	for (i=n;i;i--) sa[Ws[x[i]]--]=i;
	for (int l=1,p=0;p<n;m=p,l<<=1){
		for (i=n-l+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>l) y[++p]=sa[i]-l;
		for (i=0;i<=m;i++) Ws[i]=0;
		for (i=1;i<=n;i++) Ws[x[y[i]]]++;
		for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
		for (i=n;i;i--) sa[Ws[x[y[i]]]--]=y[i];
		swap(x,y);
		for (x[sa[1]]=p=1,i=2;i<=n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],l)?p:++p;
	}
	for (i=1;i<=n;i++) r[sa[i]]=i;
	for (i=1,k=0;i<=n;h[r[i++]]=k)
	for (k?k--:0,j=sa[r[i]-1];s[i+k]==s[j+k];k++);
}
int a[N],fa[N],ans;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool comp(int x,int y){return h[x]>h[y];}
string Q[N];int cnt;
void merge(int x){
	int a=find(sa[x]),b=find(sa[x-1]);
	fa[b]=a;S[a]|=S[b];
	if (S[a].count()*2>m){
		ans=max(ans,h[x]);
		if (ans&&ans==h[x]) Q[++cnt]=string(s+sa[x],s+sa[x]+h[x]);
	}
}
int main()
{
	freopen("Lifeforms.in","r",stdin);
	freopen("Lifeforms.out","w",stdout);
	while (1){
		scanf("%d",&m);
		if (!m) break;
		n=0;
		for (int i=1;i<=m;i++){
			scanf("%s",str);
			int L=strlen(str);
			for (int j=0;j<L;j++) s[++n]=str[j],S[n][i]=1;
			s[++n]=i+200;
		}
		getsa();ans=cnt=0;
		for (int i=1;i<=n;i++) a[i]=fa[i]=i;
		sort(a+1,a+n+1,comp);
		for (int i=1;i<=n;i++)
			if (a[i]>1) merge(a[i]);
		if (!ans) puts("?");
		sort(Q+1,Q+cnt+1);
		cnt=unique(Q+1,Q+cnt+1)-Q-1;
		for (int i=1;i<=cnt;i++) cout<<Q[i]<<endl;
		puts("");
		for (int i=1;i<=n;i++) s[i]=0,S[i].reset();
	}
	return 0;
}