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!!!! 已改正。

其他细节见代码注释

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz