【题意】
给定两个字符串A 和B,求最长公共子串的长度。
【输入】
两行,两个公共子串
【输出】
一个数字,表示最长公共子串的长度
非常经典的后缀数组应用
将两个字符串用空格连接起来
然后求后缀数组
得出height后
依次扫描height的值,输出满足两个相邻后缀的分别属于A、B的最大height
program poj2774; var n,i,j,k,a,b,m,ans:longint; root,temp:ansistring; dl,rank,sa,total,change,height,now,keep:array [-1..200001] of longint; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=dl[(s+e) div 2]; while i<=j do begin while root[dl[i]]<root[k] do inc(i); while root[dl[j]]>root[k] do dec(j); if i>j then break; swap(dl[i],dl[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; begin readln(root); a:=length(root); readln(temp); b:=length(temp); root:=root+' '+temp; n:=a+b+1; m:=a+1; for i:=1 to n do dl[i]:=i; qsort(1,n); k:=1; for i:=1 to n do begin if root[dl[i]]<>root[dl[k]] then k:=i; rank[dl[i]]:=k; end; k:=0; while 1 shl k<n do begin for i:=1 to n do if i+(1 shl k)>n then change[i]:=0 else change[i]:=rank[i+(1 shl k)]; fillchar(total,sizeof(total),0); for i:=1 to n do inc(total[change[i]]); for i:=1 to n do total[i]:=total[i]+total[i-1]; for i:=1 to n do begin dl[total[change[i]-1]+1]:=i; inc(total[change[i]-1]); end; fillchar(total,sizeof(total),0); for i:=1 to n do inc(total[rank[i]]); for i:=2 to n do total[i]:=total[i]+total[i-1]; fillchar(now,sizeof(now),0); fillchar(keep,sizeof(keep),0); for i:=1 to n do begin if now[rank[dl[i]]]<>change[dl[i]] then begin now[rank[dl[i]]]:=change[dl[i]]; total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]]; keep[rank[dl[i]]]:=0; end; inc(keep[rank[dl[i]]]); rank[dl[i]]:=total[rank[dl[i]]-1]+1; end; inc(k); end; for i:=1 to n do sa[rank[i]]:=i; fillchar(height,sizeof(height),0); for i:=1 to n do begin if rank[i]=1 then continue; k:=height[rank[i-1]]-1; if k<0 then k:=0; while (i+k<=n)and(sa[rank[i]-1]+k<=n) and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k); height[rank[i]]:=k; end; ans:=0; for i:=3 to n do if ((sa[i]>m)and(sa[i-1]<m))or((sa[i-1]>m)and(sa[i]<m)) then if height[i]>ans then ans:=height[i]; writeln(ans); end.