poj 3261 Milk Patterns (最长公共子串,后缀数组)

poj3261

题意:给一个字符串,要求找出至少出现k次的最长重复子串…

思路:后缀数组,然后再次用到了根据height数组对后缀进行分组的套路…二分判定合法性,对于当前的最长长度x,分组使得每组中的height[i]都大于等于x,所不同的是,判定变成了存在一个组,后缀的个数至少为k个(因为这样,就可以对于大于等于k个的后缀,同时取前x长度,得到的就是出现了至少k次且长度为x的前缀)1A,蛤蛤蛤

 

poj 1743 Musical Theme (不可重叠最长重复子串,后缀数组)

poj 1743

题意:n个数字(1..88)表示的音符,问最长的连续两段长度至少为5的变化相同的音符段的长度。。。

思路:求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。

先二分答案,把题目变成判定性问题:判断是否
存在两个长度为 k 的子串是相同的,且不重叠。解决这个问题的关键还是利用
height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都
不小于 k。例如,字符串为“aabaaaab”,当 k=2 时,后缀分成了 4 组,如图 5
所示。

Selection_004

容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然
后对于每组后缀,只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于
k。如果有一组满足,则说明存在,否则不存在。整个做法的时间复杂度为
O(nlogn)。本题中利用 height 值对后缀进行分组的方法很常用,请读者认真体
会。

这是论文中的题目。这个做法的确想不到,不过很好理解。

如果没有不允许重叠的条件就变成了求所有height[i]中的最大值,而每个height[i]对应的两个后缀的位置是sa[i]和sa[i-1]。

分组使得每组中的height[i]都大于等于k(那height[i]小于k的去哪里了? 因为height[i]是由两个相邻的后缀得到的,如果某两个后缀的height[i]小于k,只需要将这两个后缀分成两组,这样这个height[i]就不存在了,从而保证了每组中的height[i]都大于等于k)

而我们知道,任意两个后缀的最长公共前缀是他们之间的所有height的最小值。因为对于处于同一组内的两个后缀来说,由于之前保证了每组中的height[i]>=k,也就是保证了任意两个后缀的最长公共前缀大于等于k.

因此用二分判定长度k的时候,这样分组以后,只需要再判断是否相交(也就是如果长度k不满足,可能是因为没有办法分组使得每个height都大于等于k,也可能是存在这样的分组,但是两个后缀相交)。

判断相交其实非常简单,sa[i]表示的是排名第i的后缀的开始位置,那么如果存在sa[j]-sa[i]>=k(其实是sa[i]+k-1<sa[j],sa[i]位置开始的后缀的长度为k的前缀的最后一个字符的所在位置sa[i]+k-1比sa[j]小,就说明不相交,由于是整数,就可以变成sa[i]+k<=sa[j],也就是sa[j]-sa[i]>-=k)

而某一组内只要有一组i,j,满足sa[j]-sa[i]>=k就是有解,因此我们只需要判断最可能符合条件的一组,也就是找到一组中sa[i]的最大值和最小值,也正因为我们这样,我们在具体实现的过程中也没必要真的模拟分组的过程,只需要一直更新两个极值即可。

 

以及:lrj的板子是错的!!会re!!!! 已改正。

其他细节见代码注释

 

 

 

 

 

 

ural 1517. Freedom of Choice (后缀数组,最长公共子串)

ural1517
题意:给出两个字符串,求最长的公共字串(要求出具体的字符串是什么)

思路:依然是后缀数组,在更新长度 的时候记录起始位置即可,1A。以及,发现多开了一个完全没有必要的数组w[],这次已删。

 

20160730update:模板已更正,lrj的模板的rk[i]为0 的时候会出现re的问题…已特判。

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…