记录编号	251985	评测结果	AAAAAAAAAA
题目名称	[POJ2774]很长的信息	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.142 s
提交时间	2016-04-19 06:29:13	内存使用	21.66 MiB

#include<cstdio>
int n,s,now,tmp,ans;
struct SAM{
	int cnt,tail;
	struct node{int s[26],fa,len;}o[200010];
	inline void add(int x){
		int p,np=++cnt,q,nq;
		o[np].len=o[tail].len+1;
		for(p=tail;p&&!o[p].s[x];p=o[p].fa)o[p].s[x]=np;
		if(o[p].s[x]){
			q=o[p].s[x];
			if(o[q].len==o[p].len+1)o[np].fa=q;
			else{
				o[nq=++cnt]=o[q];
				o[q].fa=o[np].fa=nq;
				o[nq].len=o[p].len+1;
				for(;o[p].s[x]==q;p=o[p].fa)o[p].s[x]=nq;
			}
		}else o[p].s[x]=np;
		tail=np;
	}
}sam;
int main()
{
	freopen("longlongmessage.in","r",stdin);
	freopen("longlongmessage.out","w",stdout);
	s=getchar();
	while('a'<=s&&s<='z'){
		sam.add(s-97);
		s=getchar();
	}
	while(s<'a'||s>'z')
		s=getchar();
	while('a'<=s&&s<='z'){
		s-=97;
		if(sam.o[now].s[s]){
			++tmp;
			now=sam.o[now].s[s];
		}
		else{
			while(now&&!sam.o[now].s[s])
				now=sam.o[now].fa;
			if(!now&&!sam.o[now].s[s])
				tmp=0;
			else{
				tmp=sam.o[now].len+1;
				now=sam.o[now].s[s];
			}
		}
		if(ans<tmp)
			ans=tmp;
		s=getchar();
	}
	printf("%d",ans);
}