实际上可以用后缀自动机秒掉 当然后缀数组也挺好写。
我们将两个字符串接在一起，为了方便中间用一个特殊字符连接。
然后对新字符串求
heightheightheight数组。
求出来之后对所有满足
sai,sai−1sa_i,sa_{i-1}sai,sai−1属于两个不同字符串的
heightheightheight取最大值就行了。
代码：
#include #include #include #define ri register intusing namespace std;const int N=2e5+5;int n,m,len,sa[N],sa2[N],rk[N],ht[N],ans;char s[N],t[N];inline void Sort(){ static int cnt[N]; for(ri i=1;i<=m;++i)cnt[i]=0; for(ri i=1;i<=n;++i)++cnt[rk[i]]; for(ri i=2;i<=m;++i)cnt[i]+=cnt[i-1]; for(ri i=n;i;--i)sa[cnt[rk[sa2[i]]]--]=sa2[i];}inline void getsa(){ for(ri i=1;i<=n;++i)rk[i]=s[i]-'a'+1,sa2[i]=i; m=27,Sort(); for(ri w=1,p=0;m!=n;w<<=1,p=0){ for(ri i=n-w+1;i<=n;++i)sa2[++p]=i; for(ri i=1;i<=n;++i)if(sa[i]>w)sa2[++p]=sa[i]-w; Sort(),swap(sa2,rk),rk[sa[1]]=p=1; for(ri i=2;i<=n;++i)rk[sa[i]]=(sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+w]==sa2[sa[i-1]+w])?p:++p; m=p; } for(ri i=1,j,k=0;i<=n;ht[rk[i++]]=k)for(k?--k:k,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);}int main(){ scanf("%s%s",s+1,t+1),n=strlen(s+1),len=strlen(t+1),s[++n]='z'+1; for(ri i=1;i<=len;++i)s[++n]=t[i]; len=n-len-1,getsa(),ans=0; for(ri i=2,a=sa[i-1],b=sa[i];i<=n;a=sa[i],b=sa[++i]){ if(a>b)swap(a,b); if(a<=len&&b>len)ans=max(ans,ht[i]); } cout<