#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int NMax=4000,L1Max=200,LMax=NMax*(L1Max+1);
int N,L;
int A[LMax+1];
int belong[LMax];
int sa[LMax],rank[LMax],sa2[LMax],rank2[LMax],height[LMax];
void DA(){
	static int cnt[256+NMax];
	for (int i=0;i<256+N;i++)cnt[i]=0;
	for (int i=0;i<L;i++)cnt[A[i]]++;
	for (int i=1;i<256+N;i++)cnt[i]+=cnt[i-1];
	for (int i=L-1;i>=0;i--)sa[--cnt[A[i]]]=i;
	for (int i=0,j=0;i<L;i++){
		if (i && A[sa[i]]!=A[sa[i-1]])j++;
		rank[sa[i]]=j;
	}
	for (int l=1;rank[sa[L-1]]!=L-1;l+=l){
		for (int i=0;i<L;i++)cnt[rank[sa[i]]]=i+1;
		for (int i=L-1;i>=0;i--)if (sa[i]>=l)
			sa2[--cnt[rank[sa[i]-l]]]=sa[i]-l;
		for (int i=L-l;i<L;i++)
			sa2[--cnt[rank[i]]]=i;
		for (int i=0,j=0;i<L;i++){
			if (i && (rank[sa2[i]]!=rank[sa2[i-1]] || sa2[i-1]+l>=L || sa2[i]+l>=L || rank[sa2[i]+l]!=rank[sa2[i-1]+l]))j++;
			rank2[sa2[i]]=j;
		}
		for (int i=0;i<L;i++)sa[i]=sa2[i],rank[i]=rank2[i];
	}
	for (int i=0,j=0;i<L;i++){
		if (!rank[i])height[rank[i]]=0;
		else{
			int t=sa[rank[i]-1];
			while (i+j<L && t+j<L && A[i+j]==A[t+j])j++;
			height[rank[i]]=j;
			j=max(0,j-1);
		}
	}
}
int has[NMax],Q[LMax];
int main()
{
	while (scanf("%d",&N),N){
		L=0;
		for (int i=0;i<N;i++){
			static char buf[LMax];
			scanf("%s",buf);
			int l=strlen(buf);
			for (int j=0;j<l;j++){
				A[L]=(unsigned char)buf[j];
				belong[L]=i;
				L++;
			}
			A[L]=256+i;belong[L]=i;L++;
		}
		A[L]=-1;
		DA();
		int ret=0,hasc=0,retp=-1;
		for (int i=0;i<N;i++)has[i]=0;
		for (int i=0,j=0,head=0,bot=0;i<L;i++){
			if (i){
				has[belong[sa[i-1]]]--;
				if (has[belong[sa[i-1]]]==0)
					hasc--;
			}
			while (j<L && hasc<N){
				if (has[belong[sa[j]]]==0)
					hasc++;
				has[belong[sa[j]]]++;
				while (bot>head && height[Q[bot-1]]>=height[j])
					bot--;
				Q[bot++]=j++;
			}
			if (hasc<N)break;
			while (Q[head]<=i)head++;
			if (ret<height[Q[head]]){
				ret=height[Q[head]];
				retp=i;
			}
		}
		if (ret==0)puts("IDENTITY LOST");
		else{
			for (int i=0;i<ret;i++)
				putchar(A[sa[retp]+i]);
			puts("");
		}
	}
	return 0;
}

• 现在矛盾转移为static与全局变量的关系 (5) NeverLiving 2011-12-11 21:16:44
  • 找到bug了。计数排序的数组开小了。 (57) NeverLiving 2011-12-12 21:01:09