poj 2774 Long Long Message (最长公共字串,后缀数组模板题)

poj2774

题意:给出两个字符串,问最长的公共连续字串。

思路:后缀数组模板题。

具体可以参考两篇国集论文(09,04)
topcoder中的讲解
codechef上的讲解
还有一篇讲 dc3算法的论文:SuffixArrays_dc3
这里不谈具体的后缀数组的学习内容,说说大概的学习过程。

首先要理解后缀,后缀数组(sa[]),名次数组(rk[]),height数组,lcp 这些概念

先从定义入手,得到sa数组的n2logn的求法…

由于复杂度爆炸,所以有了两个算法来优化求sa的过程,一个是nlogn的倍增,还有一个是O(n)的dc3。。。

倍增的算法中用到了radix sort

上面这些,都是在说如何求sa,但是如果只有sa一个数组的话,就没有办法很好感受 后缀数组的power.

于是引入了height数组。

定义 height[i]=suffix(sa[i-1])和 suffix(sa[i])的最长公
共前缀,也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k,不妨设
rank[j]<rank[k],则有以下性质:
suffix(j) 和 suffix(k) 的 最 长 公 共 前 缀 为 height[rank[j]+1],
height[rank[j]+2], height[rank[j]+3], … ,height[rank[k]]中的最小值。

有很多问题都是基于height数组的,慢慢感受。

 

再说这道题:我们可以把两个字符串中间用一个特殊符号连接起来。

那么两个字符串的最长公共字串,就变成了求合并后的字符串的所有后缀的最长公共前缀。(原因是字符串的任何一个字串都可以看成是该字符串的某个后缀的前缀

那么容易知道,该最长公共前缀的长度一定是某个height值(原因是,height[i]表示的是排名相邻的两个后缀的最长公共前缀的长度,如果不相邻,那么取的是他们排名之间所有height的最小值,只会越来越小。

还需要注意的是,必须满足得到该height的两个后缀分别出现在原来的两个字符串中…

要怎么办到呢? 其实很容易,由于sa[i]数组存放的是排名第i的后缀是后缀几(定义从第x个字符开始的后缀就是后缀x)

设初始第一个字符串的长度为len1,那么如果是第一个字符串的后缀,一定有sa[i]<len1,如果是第二个字符串的后缀,就一定有sa[i]>len1  (sa[i]==len1的是插入的特殊符号开始的后缀)

 

还有一些细节可以参考代码注释

 

UD20160730:改正了lrj书中的错误。。对于rk[i]==0的情况进行了特判。。不然会re…

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz