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

#include <iostream>
#include <cstdio>
#include <cstring>

#define N 4010
#define A 26
#define INF 0x3f3f3f3f

using namespace std;

void file(){
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
}

namespace SAM{
	struct node{
		node *ch[A],*fa;
		int len,minv,maxv;
	}*root,*last,spT[N],*b[N];
	
	int tot,cnt[N],ans;
	
	void init(){
		root=&spT[tot=1];
		last=root;
	}
	
	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];
	}
	
	void addin(char c){
		int t=c-'a';
		node *np=&spT[++tot],*p=last;
		np->len=last->len+1;
		np->minv=np->len;
		last=np;
		for(;p&&!p->ch[t];p=p->fa) p->ch[t]=np;
		if(!p) np->fa=root;
		else{
			if(p->len+1==p->ch[t]->len) 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;
				nq->minv=nq->len;
				for(;p&&p->ch[t]==q;p=p->fa)
					p->ch[t]=nq;
			}
		}
	}
	
	void ask(char* S,int n){
		int len=0;
		node* p=root;
		for(int i=1;i<=tot;i++) b[i]->maxv=0;
		for(int i=0;i<n;i++){
			int t=S[i]-'a';
			if(p->ch[t]) p=p->ch[t],len++;
			else{
				for(;p&&!p->ch[t];p=p->fa);
				if(!p) p=root,len=0;
				else len=p->len+1,p=p->ch[t];
			}
			p->maxv=max(p->maxv,len);
		}
		ans=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);
			ans=max(ans,tmp->minv);
		}
	}
}

int n,T;
char S[N];

int main(){
	file();
	scanf("%d%s",&n,S);
	SAM::init();
	n=strlen(S);
	for(int i=0;i<n;i++) SAM::addin(S[i]);
	SAM::topsort(n);
	while(scanf("%s",S)==1) SAM::ask(S,strlen(S));
	printf("%d\n",SAM::ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}