记录编号	170692	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2015-07-15 07:39:24	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
#define Nil NULL//Orz 光神!
const int SIZE=20010;
class Suffix_Automaton{
public:
	class Node{
	public:
		int len;
		Node *suflink;
		Node *ch[31];
		bitset<31> reach;
		Node(){
			len=0;
			suflink=Nil;
			memset(ch,0,sizeof(ch));
		}
	};
	Node *root,*last;
	int n;
	Node* lis[SIZE];
	int findpos(Node *a){
		if(!a) return -1;
		for(int i=0;i<n;i++){
			if(lis[i]==a) return i;
		}
		return -2;
	}
	void print(Node *a){
		cout<<"地址:"<<findpos(a)<<endl;
		cout<<"len:"<<a->len<<endl;
		cout<<"suflink:"<<findpos(a->suflink)<<endl;
		for(int i=0;i<31;i++){
			if(a->ch[i]!=Nil){
				cout<<(char)('a'+i)<<" :"<<findpos(a->ch[i])<<endl;
			}
		}
		cout<<"reach list:";for(int i=0;i<31;i++){if(a->reach[i]){cout<<(char)('a'+i);}}cout<<endl;
		cout<<endl;
	}
	void clear(void){
		root=new Node();
		last=root;
		lis[0]=root;
		n=1;
	}
	Suffix_Automaton(void){clear();}
	void Insert(char c){
		int k=c-'a';
		Node *cur=new Node();
		lis[n++]=cur;
		cur->len=last->len+1;
		Node *p=last;
		while(p!=Nil&&p->ch[k]==Nil){
			p->ch[k]=cur;
			p=p->suflink;
		}
		if(p==Nil) cur->suflink=root;
		else{
			Node *q=p->ch[k];
			if(q->len==p->len+1) cur->suflink=q;
			else{
				Node *clone=new Node();
				lis[n++]=clone;
				*clone=*q;
				clone->len=p->len+1;
				cur->suflink=clone;
				q->suflink=clone;
				while(p!=Nil&&p->ch[k]==q){
					p->ch[k]=clone;
					p=p->suflink;
				}
			}
		}
		last=cur;
	}
	class cmp{//排个序真麻烦......
	public:
		bool operator () (Node *a,Node *b){
			return a->len<b->len;
		}
	};
	int calc_LCS(int dnum){
		int ans=0;
		sort(lis,lis+n,cmp());
		for(int i=n-1;i>=0;i--){
			Node *p=lis[i];
			if(p->suflink!=Nil) p->suflink->reach|=p->reach;
			for(int k=0;k<26;k++)
				if(p->ch[k]!=Nil)
					p->reach|=p->ch[k]->reach;
			for(int k=26;k<31;k++)
				if(p->ch[k]!=Nil)
					p->reach[k]=true;
			bool flag=true;
			for(int k=26;k<26+dnum;k++)
				if(!p->reach[k]) flag=false;
			if(flag) ans=max(ans,p->len);
		}
		return ans;
	}
}M;
int N;
char str[SIZE]={0};
int main(){
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%s",str);
		int L=strlen(str);
		str[L]='z'+i;
		for(int i=0;i<=L;i++)
			M.Insert(str[i]);
	}
	printf("%d\n",M.calc_LCS(N));
	return 0;
}