#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=250010;
const int MAXS=26;
typedef struct node* star;
struct node{
int l;
star p,ch[MAXS];
node(){}
node(int l,star p):l(l),p(p){
memset(ch,0,sizeof(ch));
}
}pool[MAXN<<1];
star tail,rt,cur;
int n,m;
char A[MAXN],B[MAXN];
inline void Build(){
tail=pool;
cur=rt=tail++;
*rt=node(0,0);
for(int i=0;i<n;++i){
int x=A[i]-'a';
star p=cur;
cur=tail++;
*cur=node(i+1,0);
for(;p&&!p->ch[x];p=p->p)
p->ch[x]=cur;
if(!p)cur->p=rt;
else{
star q=p->ch[x];
if(q->l==p->l+1)
cur->p=q;
else{
star r=tail++;
*r=*q;
r->l=p->l+1;
cur->p=q->p=r;
for(;p&&p->ch[x]==q;p=p->p)
p->ch[x]=r;
}
}
}
}
int ans;
int main(){
scanf("%s%s",A,B);
n=strlen(A); m=strlen(B);
Build();
cur=rt;
for(int i=0,l=0;i<m;++i){
int x=B[i]-'a';
if(cur->ch[x]){
++l;
cur=cur->ch[x];
}
else{
for(;cur&&!cur->ch[x];cur=cur->p);
l=cur?cur->l+1:0;
cur=cur?cur->ch[x]:rt;
}
if(ans<l)ans=l;
}
printf("%d\n",ans);
return 0;
}
评论0