记录编号	214598	评测结果	RRRRRRRRRR
题目名称	[HZOI 2015] Glass Beads	最终得分	0
用户昵称	0	是否通过	未通过
代码语言	C++	运行时间	0.014 s
提交时间	2015-12-16 20:35:59	内存使用	21.75 MiB

#include<cstdio>
#include<cstring>

#define maxn 100010

using namespace std;

int cnt,n,last;
char s[maxn];

inline int MAX(int a,int b){ return a>b?a:b; }

struct Suffix{
	int son[maxn<<1][26],pre[maxn<<1],step[maxn<<1];
	void push(int p){ step[++cnt]=p;return; }
	void Extend(int ch){
		push(step[last]+1);
		int np=cnt,p=last,q,nq;
		for(;!son[p][ch];p=pre[p]) son[p][ch]=np;
		if(!p&&son[0][ch]==np) pre[np]=0;
		else{
			q=son[p][ch];
			if(step[q]==step[p]+1) pre[np]=q;
			else{
				push(step[p]+1);
				nq=cnt;
				memcpy(son[nq],son[q],sizeof(son[q]));
				pre[nq]=pre[q];
				pre[q]=pre[np]=nq;
				for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq;
			}
		}
		last=np;
		return;
	}
	void build(){
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;i++){
			Extend(s[i]-'a');
		}
	}
	void solve(){
		scanf("%s",s+1);
		n=strlen(s+1);
		int p=0,tmp=0,ans=0;
		for(int i=1;i<=n;i++){
			int idx=s[i]-'a';
			if(son[p][idx]) tmp++,p=son[p][idx];
			else{
				while(p&&!son[p][idx]) p=pre[p];
				if(!p) tmp=0;
				else tmp=step[p]+1,p=son[p][idx];
			}
			ans=MAX(ans,tmp);
		}
		printf("%d",ans);
	}
}SAM;

int main()
{
	freopen("longlongmessage.in","r",stdin);
	freopen("longlongmessage.out","w",stdout);
	SAM.build();
	SAM.solve();
	return 0;
}