POJ后缀数组相关整理

本篇文章仅总结POJ上能够用后缀数组这一数据结构解决的问题类型以及解决思路,并不提供代码。

后缀数组是算法竞赛之中常见的一种数据结构。相对后缀树而言,它显得简洁而又强大。初学后缀数组,你会发现即便了解了原理,告诉了你这道题是后缀数组,你也不一定能将它做出来,更别提在比赛中遇到了。这也是我这两天所面对的窘境。在这里我将POJ上的一些后缀数组相关题目摘抄下来,抽象成具体的问题,并对其进行分析解答,以求在纷乱繁杂的题目中窥得一丝规律。

 

POJ – 2774  Long Long Message

这道题的题面就很长,不过简而言之,就是求两个字符串的最长公共子串。最开始考虑使用动态规划来求解,但(100000*100000)的复杂度显然是远远不能满足我们的需求的。

所以考虑使用后缀数组进行解题。这里要利用后缀数组中的height数组,它代表字典序相邻两个后缀的重复子串长度。我们应该能想到要将两个字符串连到一起,然后跑一遍后缀数组,求解height的最大值。一个比较特殊的方法是,在连接好的两个字符串之间用一个在这个字符串中不会出现的字符隔开。这样处理之后就可以判断要不要更新maxheight的值——如果sa[i]和sa[i-1]一个属于第一个字符串一个属于第二个字符串,即可判断这个height值是合法可以更新的。

 

POJ – 3450  Corporate Identity

这道题与上道题基本一样,只是要求多个字符串的最长公共子串长度。像刚才一样,我们把所有字符串连接起来并分割开。但这时就不能在一个一个判断height值了,因为涉及到好几个height值。我们考虑一种常见的思路——先猜答案,再对答案进行验证是否正确,也就是二分验证的思想。我们二分公共子串的长度,并对所有相邻后缀查看是否有连续n个后缀的height值大于我们的枚举值,并且还同时分属于n个不同的字符串。

 

POJ – 3581 Sequence

题意如下,给我们一个序列,我们要将它切成三个子序列并且满足将这三个子序列进行翻转操作后的字典序最小。说到字典序最小,就想到后缀数组的排列就是按字典序。此时我们把整个序列翻转,跑一遍后缀数组,从头开始搜字典序最小的后缀。即可得到我们要切割出来的第一个部分,要注意这个部分的下标一定要大于1(如果下标从0开始),否则剩下的部分就切不成两部分了。

接下来的任务就是把剩下的两个部分切开。能够想到的方法是再跑一遍后缀数组,然而这里又有一个坑——如果直接搜索的话,会出现由于字符串长度而导致的字典序错乱问题,比如要将2 0 1 0 1(翻转后的)分成两部分,直接做后缀数组得到的解应该是0 1,那么答案就是0 1 2 0 1,但显然答案应该是0 1 0 1 2,问题就出在最小字典序的0 1 0 1因为长度比0 1长导致其在字典序中靠后,所以我们将原子符串翻倍,以此来模拟最后的结果,这样就不会再出现这样的问题了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注