level 5
Program poj2774;
Var i,j,k,m,n,l,p,mi,ans:longint;
s1,s2,str:ansistring;
sum,sa,tsa,rk,trk,h:array[0..210000] of longint;
Begin
readln(s1); readln(s2);
str:=s1+*$*+s2;
mi:=length(s1)+1;
l:=length(str);
for i:=1 to l do
begin
trk[i]:=ord(str[i]); inc(sum[trk[i]]);
end;
for i:=2 to 255 do
begin
inc(sum[i],sum[i-1]);
end;
for i:=l downto 1 do
begin
sa[sum[trk[i]]]:=i; dec(sum[trk[i]]);
end;
rk[sa[1]]:=1; p:=1;
for i:=2 to l do
begin
if trk[sa[i]]<>trk[sa[i-1]] then inc(p);
rk[sa[i]]:=p;
end;
m:=p; j:=1;
while m<l do
begin
move(rk,trk,sizeof(rk));
fillchar(sum,sizeof(sum),0);
p:=0;
for i:=l-j+1 to l do begin inc(p); tsa[p]:=i; end;
for i:=1 to l do
if sa[i]>j then
begin inc(p); tsa[p]:=sa[i]-j; end;
for i:=1 to l do begin rk[i]:=trk[tsa[i]]; inc(sum[rk[i]]); end;
for i:=2 to m do inc(sum[i],sum[i-1]);
for i:=l downto 1 do begin sa[sum[rk[i]]]:=tsa[i]; dec(sum[rk[i]]); end; rk[sa[1]]:=1; p:=1;
for i:=2 to l do begin
if (trk[sa[i]]<>trk[sa[i-1]]) or (trk[sa[i]+j]<>trk[sa[i-1]+j]) then begin
inc(p); rk[sa[i]]:=p; end;
end;
m:=p; j:=j*2;
end;
h[1]:=0; p:=0;
for i:=1 to l do
begin
if rk[i]=1 then continue;
j:=sa[rk[i]-1];
if (i+p<=l) and (j+p<=l) then
while str[i+p]=str[j+p] do
begin
inc(p);
if (i+p)>l then break;
if (j+p)>l then break;
end;
h[rk[i]]:=p;
if p>0 then dec(p);
end;
for i:=2 to l do
begin
if h[i]>ans then
if ((sa[i]<mi) and (sa[i-1]>mi)) or ((sa[i]>mi) and (sa[i-1]<mi)) then ans:=h[i];
end;
writeln(ans);
End.
2014年08月02日 12点08分

