好像已经很久没有做后缀数组的题目，导致这种题一开始没想出来
看到公共子串肯定想到后缀数组吧，但我都忘了最长公共子串怎么求了
重要的性质：最长公共子串=max(h[i]）名次相邻的两个后缀要分别属于s1,s2串 具体怎么证很简单
这道题多了一个条件，就是公用子串不能包含某个串——很明显想到KMP
我们可以预处理与s3匹配的起始位置，然后处理每个点右边最近的起始位置
然后在穷举h[i]的时候判断一下即可
var h,f,x,y,sum,sa,rank:array[..] of longint;
v:array[..] of boolean;
j,t,st,en,ans,i,p,l,n,m:longint;
s,ss:ansistring;
fl:boolean; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure suffix;
var i,p,j,m:longint;
begin
m:=;
for i:= to n do
begin
y[i]:=ord(s[i]);
inc(sum[y[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[y[i]]]:=i;
dec(sum[y[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if y[sa[i]]<>y[sa[i-]] then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
y:=rank;
fillchar(sum,sizeof(sum),);
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i]>j then
begin
inc(p);
x[p]:=sa[i]-j;
end;
for i:= to n do
begin
rank[i]:=y[x[i]];
inc(sum[rank[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[rank[i]]]:=x[i];
dec(sum[rank[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (y[sa[i]]<>y[sa[i-]]) or (y[sa[i-]+j]<>y[sa[i]+j]) then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=j shl ;
end;
p:=;
h[]:=;
for i:= to n do
begin
if rank[i]= then continue;
j:=sa[rank[i]-];
while s[i+p]=s[j+p] do inc(p);
h[rank[i]]:=p;
if p> then dec(p);
end;
end; begin
readln(s);
readln(ss);
p:=length(s)+;
s:=s+chr()+ss+chr();
n:=length(s); readln(ss);
l:=length(ss);
ss:=ss+' ';
for i:= to l do
begin
j:=f[i-];
while (j>) and (ss[j+]<>ss[i]) do j:=f[j];
if ss[j+]=ss[i] then f[i]:=j+ else f[i]:=;
end; j:=;
for i:= to p- do
begin
while (j>) and (ss[j+]<>s[i]) do j:=f[j];
if ss[j+]=s[i] then
begin
inc(j);
if j=l then v[i-l+]:=true;
end
else j:=;
end; t:=;
for i:=p- downto do
begin
if v[i] then t:=i;
f[i]:=t; //右边最近的匹配起始节点
end;
suffix;
ans:=;
for i:= to n do
begin
fl:=false;
if (sa[i]<p) and (sa[i-]>p) and (sa[i-]<n) then
begin
st:=sa[i];
en:=f[st];
fl:=true;
end;
if (sa[i]>p) and (sa[i]<n) and (sa[i-]<p) then
begin
st:=sa[i-];
en:=f[st];
fl:=true;
end;
if fl then
begin
if h[i]>=en-st+l then //判断是否包含了匹配串
ans:=max(ans,en-st+l-)
else ans:=max(ans,h[i]);
end;
end;
writeln(ans);
end.