记录编号	377957	评测结果	AAAAAAAAAA
题目名称	1713.[POJ2774]很长的信息	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2017-03-02 18:38:24	内存使用	32.64 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define eps 1e-8
const int maxn=150000;
struct SAM{
	int root,val;
	int next[26];
}a[maxn<<1];
int cnt,RT,last;
char s1[maxn],s2[maxn];
void Extend(int c){
	int p=last,np=++cnt;
	a[np].val=a[p].val+1;
	while(p && !a[p].next[c]){
		a[p].next[c]=np;
		p=a[p].root;
	}
	if(!p)a[np].root=RT;
	else {
		int q=a[p].next[c];
		if(a[q].val==a[p].val+1)a[np].root=q;
		else {
			int nq=++cnt;
			a[nq]=a[q];
			a[nq].val=a[p].val+1;
			a[q].root=a[np].root=nq;
			while(p && a[p].next[c]==q){
				a[p].next[c]=nq;
				p=a[p].root;
			}
		}
	}
	last=np;
}
void Init();
int main(){
	freopen("longlongmessage.in","r",stdin);
	freopen("longlongmessage.out","w",stdout);
    Init();
    return 0;
}
void Init(){
	scanf("%s%s",s1,s2);
	last=RT=++cnt;
	int len1=strlen(s1);
	int len2=strlen(s2);
	for(int i=0;i<len1;i++)Extend(s1[i]-'a');
	int p=RT,tmp=0,ans=0;
	for(int i=0;i<len2;i++){
		if(a[p].next[s2[i]-'a']){
			p=a[p].next[s2[i]-'a'];tmp++;
		}
		else {
			while(p && !a[p].next[s2[i]-'a'])p=a[p].root;
			if(!p)p=RT,tmp=0;
			else tmp=a[p].val+1,p=a[p].next[s2[i]-'a'];
		}
		ans=max(ans,tmp);
	}
	printf("%d\n",ans);
}