记录编号	170874	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-07-16 20:21:12	内存使用	7.15 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

#define LL long long
#define N 30010
#define INF 0x3f3f3f3f

using namespace std;

namespace SAM{
	struct node{
		node *ch[26],*fa;
		int len,maxv,minv;
	}*root,spT[N<<1],*now,*b[N<<1];
	
	int tot,ansv;
	int cnt[N];
	
	void init(){
		tot=0;
		root=&spT[++tot];
		now=root;
	}
	
	int idx(char c){
		return c-'a';
	}
	
	void topsort(int n){
		for(int i=1;i<=tot;i++) cnt[spT[i].len]++;
		for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for(int i=1;i<=tot;i++) b[cnt[spT[i].len]--]=&spT[i];
		for(int i=1;i<=tot;i++) b[i]->minv=b[i]->len;
	}
	
	void addin(char c){
		int t=idx(c);
		node *np=&spT[++tot],*p=now;
		now=np;
		np->len=p->len+1;
		for(;p&&!p->ch[t];p=p->fa) p->ch[t]=np;
		if(!p) np->fa=root;
		else{
			if(p->ch[t]->len==p->len+1) np->fa=p->ch[t];
			else{
				node* nq=&spT[++tot],*q=p->ch[t];
				*nq=*q;
				q->fa=np->fa=nq;
				nq->len=p->len+1;
				for(;p&&p->ch[t]==q;p=p->fa)
					p->ch[t]=nq;
			}
		}
	}
	
	void ask(char *S,int n){
		node* p=root;
		int tmp=0;
		for(int i=1;i<=tot;i++) b[i]->maxv=0;
		for(int i=0;i<n;i++){
			int t=idx(S[i]);
			if(p->ch[t]) tmp++,p=p->ch[t];
			else{
				for(;p&&!p->ch[t];p=p->fa);
				if(!p) p=root,tmp=0;
				else tmp=p->len+1,p=p->ch[t];
			}
			p->maxv=max(p->maxv,tmp);
		}
		ansv=0;
		for(int i=tot;i>=1;i--){
			node* tmp=b[i];
			if(tmp->fa) tmp->fa->maxv=max(tmp->fa->maxv,tmp->maxv);
			tmp->minv=min(tmp->minv,tmp->maxv);
			ansv=max(ansv,tmp->minv);
		}
	}
}

char S[N];
int n;

int main(){
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",S);
	n=strlen(S);
	SAM::init();
	for(int i=0;i<n;i++) SAM::addin(S[i]);
	SAM::topsort(n);
	while(scanf("%s",S)==1){
		n=strlen(S);
		SAM::ask(S,n);
	}
	printf("%d\n",SAM::ansv);
	fclose(stdin);
	fclose(stdout);
	return 0;
}