【codevs3160】最长公共子串

2015年2月6日3,3376
题目描述 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

 

  • 吴桐2015年1月16日 下午12:47 回复

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

    #1  
  • huanghongxun2015年4月7日 下午1:30 回复

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

    #2  
  • jxrjxrjxr2015年11月17日 下午9:31 回复

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

    #3  
    • hzwer2015年11月17日 下午10:28 回复
      admin

      这个我怎么解释。。。你看看论文?

      #31
    • orzwzh2015年11月18日 上午7:28 回复

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

      #31
      • jxrjxrjxr2015年11月21日 下午5:18 回复

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

        #32