记录编号	231297	评测结果	AAAAAAAAAA
题目名称	[POJ2774]很长的信息	最终得分	100
用户昵称	hsez_jxr	是否通过	通过
代码语言	C++	运行时间	0.283 s
提交时间	2016-02-26 08:02:48	内存使用	19.66 MiB

#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;

int S,size,las;
int len[2*N],ch[2*N][26],par[2*N];
void add(int c)
{
	int p=las,np=las=++size;
	for(len[np]=len[p]+1;p&&!ch[p][c];p=par[p]) ch[p][c]=np;
	if(!p) return par[np]=S,void(0); int q=ch[p][c];
	if(len[q]==len[p]+1) return par[np]=q,void(0);
	int r=++size; len[r]=len[p]+1,par[r]=par[q],par[q]=par[np]=r;
	for(memcpy(ch[r],ch[q],sizeof(ch[q]));p&&ch[p][c]==q;p=par[p]) ch[p][c]=r;
}

char A[N],B[N];
int main()
{
	freopen("longlongmessage.in","r",stdin);
	freopen("longlongmessage.out","w",stdout);
	S=size=las=1;
	scanf("%s%s",A,B);
	int n=strlen(A);
	int m=strlen(B);
	for(int i=0;i<n;i++)
		add(A[i]-'a');
	int x=S,cur=0,ans=0;
	for(int i=0;i<m;i++)
	{
		int c=B[i]-'a';
		if(ch[x][c]) x=ch[x][c],cur++;
		else
		{
			while(x&&!ch[x][c]) x=par[x];
			if(x) cur=len[x]+1,x=ch[x][c];
			else x=S,cur=0;
		} if(ans<cur) ans=cur;
	}printf("%d\n",ans);
	return 0;
}