记录编号	155845	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2015-03-31 09:30:40	内存使用	0.52 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=10100;
int n,length=0,k;
int sa[MAXN],rank[MAXN],trank[MAXN],h[MAXN];
int position[MAXN];
bool Exist[15];
char str[MAXN];
string str1,str2;
///==============function declaration============
bool cmp1(int a,int b){return str[a]<str[b];}
bool cmp2(int a,int b){return rank[a]==rank[b]?rank[a+(1<<k)]<rank[b+(1<<k)]:rank[a]<rank[b];}
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("pow.in","r",stdin);
   freopen("pow.out","w",stdout);
	//#endif 
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>str1;
		str2=str2+str1+'$';
	}
	strcpy(str+1,str2.c_str());
	length=strlen(str+1);
	int buf=1;
	for(int i=1;i<=length;i++){
		if (str[i]=='$'){
			buf++;
			str[i]='0'+buf-1;
		}
		else
			position[i]=buf;
	}
	for(int i=1;i<=length;i++)
		sa[i]=i;
	sort(sa+1,sa+1+length,cmp1);
	rank[sa[1]]=1;
	for(int i=2;i<=length;i++)
		if (str[sa[i]]==str[sa[i-1]])
			rank[sa[i]]=rank[sa[i-1]];
		else
			rank[sa[i]]=rank[sa[i-1]]+1;
	length=strlen(str+1);
	for(k=0;(1<<k)<=length;k++){
		sort(sa+1,sa+1+length,cmp2);
		trank[sa[1]]=1;
		for(int i=2;i<=length;i++)
			if (rank[sa[i]]==rank[sa[i-1]]&&rank[sa[i]+(1<<k)]==rank[sa[i-1]+(1<<k)])
				trank[sa[i]]=trank[sa[i-1]];
			else
				trank[sa[i]]=trank[sa[i-1]]+1;
		for(int i=1;i<=length;i++)
			rank[i]=trank[i];
		if (rank[sa[length]]==length) break;
	}
	///计算sa[rank[i]]和sa[rank[i]-1]的最长公共前缀
	for(int i=1;i<=length;i++){
		h[rank[i]]=max(0,h[rank[i-1]]-1);
		int p=sa[rank[i]],q=sa[rank[i]-1];
		while (str[p+h[rank[i]]]==str[q+h[rank[i]]])
			h[rank[i]]++;
	}
	/*for(int i=1;i<=length;i++){
		printf("sa[%d]=",i);
		for(int j=sa[i];j<length;j++)
			printf("%c",str[j]);
		printf(" %d\n",h[i]);
	}*/
			  
	int _ans=0;
	for(int i=1;i<=length;i++){
		if (h[i+1]>=h[i]) continue;
		int x=i,_min=h[i];
		memset(Exist,false,sizeof(Exist));
		bool suc=false;int cnt=1;
		Exist[position[sa[i]]]=true;
		for(int j=i;j>=1;j--){
			if (!Exist[position[sa[j-1]]]){
				 Exist[position[sa[j-1]]]=true;
				 cnt++;
			}
			_min=min(_min,h[j]);
			if (cnt==n){
				_ans=max(_ans,_min);
				break;
			}
			if (_min==0) break;
		}
	}
	printf("%d\n",_ans);
   return 0;
}
///================fuction code====================