「CODEVS3160」最长公共子串

2015年2月6日3,9357
题目描述 Description

给出两个由小写字母组成的字符串,求它们的最长公共子串的长度。

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入 Sample Input
样例输出 Sample Output

27

数据范围及提示 Data Size & Hint

单个字符串的长度不超过100000

题解

算法1:后缀数组

同poj2774

bzoj挂了没事干。。。

2014.9.21 *1

2015.2.6 *1

算法2:后缀自动机

将第一个串建sam后第二个串在上面匹配QAQ

 

说点什么

提醒
avatar
enfris

hzwer大神!我发现这份后缀自动机代码有点小问题
solve函数中定义了now=1但是用的是p节点转移,所以这组数据就WA了:
dddddddddddda
a

jxrjxrjxr
jxrjxrjxr

for(int i=n;i>=0;i–) if(sa[i]>k) SA[v[rk[sa[i]-k]]–]=sa[i]-k;
这句是什么意思,求解释

orzwzh

v记录之前的每一个rank最后出现的位置。。然后你从后往前枚举,对每个相同的前半部分,一定先找到后半部分最大的。。然后他就应该放在当前最大的位置。。

jxrjxrjxr
jxrjxrjxr

看到09年论文貌似懂了。。

huanghongxun

是后缀自动机快还是DC3快→_→

吴桐

论文上说有一个奇怪的不用二分的方法,打了之后发现wa了三个,求解释