原文链接https://www.cnblogs.com/zhouzhendong/p/9253173.html
题目传送门 - BZOJ3796
题意
找一个串 $w$ 满足：
1、$w$ 是 $s_1$ 的子串
2、$w$ 是 $s_2$ 的子串
3、$s_3$ 不是 $w$ 的子串
4、$w$ 的长度应尽可能大
输出 $w$ 的长度。
$|s_1|,|s_2|\leq 50000,|s_3|\leq 10000$
题解
考虑求两个串 $(s_1,s_2)$ 的最长公共子串，我们可以把他们用一个特殊字符隔开，然后跑一下 $SA$ .。
然后请你自行证明最长的一定是一个 $height[i]$ ，满足 $SA[i],SA[i-1]$ 这两个位置分别在 $s_1$ 和 $s_2$ 中。
再考虑加上 $s_3$ 的限制。
我们 $KMP$ 一下，看看从哪些位置开始，$s_3$ 与由 $s_1,s_2$ 构成的母串重合。
然后预处理出对于母串的每一个位置，下一个重合点最早出现在哪里，记为 $e[i]$ ，于是从当前位置开始的串长不能超过 $e[i]-i+|s_3|-1$ ，最后统计 $height$ 的时候取个 $\min$ 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int m,n,l,fail[N],e[N];
int SA[N],tmp[N],rank[N],height[N],tax[N];
char s[N],t[N];
void KMP(){
fail[0]=0,fail[1]=0;
for (int i=2;i<=l;i++){
int f=fail[i-1];
while (f>0&&t[f+1]!=t[i])
f=fail[f];
fail[i]=f+(t[f+1]==t[i]);
}
int k=0;
for (int i=1;i<=n;i++){
while (k>0&&t[k+1]!=s[i])
k=fail[k];
k+=(t[k+1]==s[i]);
if (k==l)
k=fail[k],e[i-l+1]=i-l+1;
}
}
void Sort(int n,int m){
for (int i=0;i<=m;i++)
tax[i]=0;
for (int i=1;i<=n;i++)
tax[rank[i]]++;
for (int i=1;i<=m;i++)
tax[i]+=tax[i-1];
for (int i=n;i>=1;i--)
SA[tax[rank[tmp[i]]]--]=tmp[i];
}
bool cmp(int rk[],int x,int y,int w){
return rk[x]==rk[y]&&rk[x+w]==rk[y+w];
}
void Suffix_Array(char s[],int n){
memset(SA,0,sizeof SA);
memset(tmp,0,sizeof tmp);
memset(rank,0,sizeof rank);
memset(height,0,sizeof height);
int m=200;
for (int i=1;i<=n;i++)
rank[i]=s[i],tmp[i]=i;
Sort(n,m);
for (int w=1,p=0;p<n;w<<=1,m=p){
p=0;
for (int i=n-w+1;i<=n;i++)
tmp[++p]=i;
for (int i=1;i<=n;i++)
if (SA[i]>w)
tmp[++p]=SA[i]-w;
Sort(n,m);
swap(tmp,rank);
rank[SA[1]]=p=1;
for (int i=2;i<=n;i++)
rank[SA[i]]=cmp(tmp,SA[i],SA[i-1],w)?p:++p;
}
for (int i=1,j,k=0;i<=n;height[rank[i++]]=k)
for (k=max(k-1,0),j=SA[rank[i]-1];s[i+k]==s[j+k];k++);
height[1]=0;
}
bool Type(int x){
return x>m;
}
int main(){
scanf("%s",s+1);
m=strlen(s+1)+1;
s[m]='*';
scanf("%s",s+m+1);
n=strlen(s+1);
scanf("%s",t+1);
l=strlen(t+1);
for (int i=1;i<=n;i++)
e[i]=n+1;
KMP();
for (int i=n-1;i>=1;i--)
e[i]=min(e[i],e[i+1]);
Suffix_Array(s,n);
int ans=0;
for (int i=2;i<=n;i++)
if (Type(SA[i])^Type(SA[i-1]))
ans=max(ans,min(height[i],e[SA[i]]-SA[i]+l-1));
printf("%d",ans);
return 0;
}