【题意】
给定两个字符串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;
......
阅读全文