现在的位置: 首页 > 综合 > 正文

后缀数组题目集锦

2012年03月17日 ⁄ 综合 ⁄ 共 2475字 ⁄ 字号 评论关闭

基础题 :

      论文其实写的很详细了,但是模板可能有点难看懂,需要花点时间去搞,建议一开始的时候写个nlogn^2的算法,推荐watashi翻译的那本书里面的讲解与代码实现,灰常清晰,其实也就是倍增排序的时候用快速排序来做,虽然时间上慢了点,但是对深刻理解SA
RANK HEIGHT这三个数组有很大的好处,比赛的时候还是用论文里面的模板吧,速度快。

     对模板的熟悉,以及对sa数组,rank数组,height数组的理解,这三个数组是解决很多后缀问题的利器。

一些代码放在这里:http://blog.csdn.net/crazy_ac/article/details/9857273

part1 :论文题 

           最长重复子串: 稍微想一下就知道了,高度数组的最大值就是答案

             不可重叠最长重复子串 :
 
 


                            直接做比较难,先二分,然后变成判定性问题。


                 求至少出现k次的最长重复子串(可重叠)

                                    同上,二分变成判定性问题后分组,将最长公共前缀大于等于mid的分在同一组,只要判断是否有一组的数量大于等于k,不过这个题数比较弱,m值设成128也能AC,实测表示,数据中连大于128的数也没有。


                   求不同子串的个数1 求不同子串的个数2 


                                   将后缀排好序后,从上往下扫描,累加以s[sa[i]]开头的字符串,注意最长公共前缀的部分要去掉,因为在上一次已经算过了。

                 求最长回文子串 


                                   很经典的题,虽然数据范围比较小,但是还是可以用来锻炼后缀数组。重新做的时候还是想了老半天。。。。

                          解法:假设我们知道了回文子串的中心,假设是奇数个字符,那么求最长回文子串就是求以某个中心往两端最长能扩充的距离,而且一直都相等,如果将字符串倒过来,就是相当于求两个后缀的最长公共前缀了,具体实现时要用到RMQ求区间最值,还要考虑奇偶性,不过还是挺好写的。

                  求重复次数最多且字典序最小的子串 


        此题非常赞,可以通过枚举循环节的长度来做。

             关键点:s[0],s[L],s[L*2]....一定会经过重复子串中的相邻两个循环节。输出字典序最小没什么思路,最后搜了下,发现是从字典序最小的后缀开始,然后 枚举所有可能的长度来做的,好暴力。。


                   求两个字符串大于等于k的公共子串的对数

                  此题大赞!利用了一个性质:所有的排名在当前串(假设是B串)之前的A串跟当前串的最长公共前缀是非递减的!所以假设前面一系列的最长公共前缀是5 7 8 9,然后突然出现一个2,那么直接将前面多余的那一部分砍掉就好了,因为当前的2已经是最大的公共前缀了,其他的已经没用了。所以动态的维护一个长度的总和就好了,怕混在一起写不清楚,我是分两次遍历的,一次统计A->B  ,另一次反过来。


如上图,1 2 3,加进来的时候会不断的扩展(进栈),4加进来的时候直接砍掉前面的多余的部分就好了(退栈)


        按照字典序输出所有的最长的且在一半以上字符串中出现的子串

         又是一个二分之后扫描一遍的题目,比较水


        求最长不重叠的重复子串的长度,要求在每个字符串中至少出现两次。


          还是二分+扫描验证,验证的时候判断是否有一组后缀在每个字符串中都有出现两次,而且不重叠。

             至此,论文题已被A完,仔细思考发现二分长度是很常用的一种方法!

 part 2  : 各大oj游走

Codeforces

           求字典序第k大的子串

                          这个题有两种做法,一种是用堆 , 另一种是用后缀数组,思想是一样的,提示:从每个位置开始不断地往后面扩展字符串。

                         
后缀数组
       

poj :

                poj  3581 

                  将一个数字序列分割成非空的三段,然后各自反转,输出字典序最小的序列第一个数字是最大的。

                          1:   这个题个人感觉还是很好的一个题。一开始看到分成三段毫无想法,但是利用好第一个数字是最大的这个条件的话可以去掉将问题简化,因为第一个数字是最大的,所以反转后找到字典序最小的第一个满足条件的后缀就是第一个分割点的方案了,满足条件是指,第一个分割位置p1应该在最后两个数之前(因为后面还要分割一次),由于第一个数字是最大的,所以这样贪心的选取第一个位置就OK了(仔细想想就知道了)。然后的问题就是一般化的,给你一个字符串,找到一个位置将其分割,各自反转,使得最终的字符串字典序最小,这个其实也挺简单的,只要将字符串反转,复制两次就好了。现在,每一种分割方案都对应了当前字符串的一个子串,排名在最前面而且的满足条件的后缀肯定就对应了最小字典序的分割方案,所以从小到大再次找到一个满足条件的后缀就好了。

                          2: 用最小表示法可以秒切这道题。看到discuss里面有人说就随手学,随手敲了。

 light oj:                 

         
求一个字符串不同子串的个数,而且长度在[p,q]之间

                                 求出height数组后扫一遍。。。

         
求三个串的最长公共子串

                     two_pointers,搞个变量移动一下,然后用rmq查询区间最值,我比较懒,直接用了个set。

         
求第一个串中有多少的子串不包含B串

                               先用kmp匹配出所有的非法位置,然后线性扫描,注意细节就好。

BZOJ:

         3238

         

挺简单的一道题呢,听说要什么笛卡尔树,但用RMQ也过了,首先可以想到排序之后一段区间内两两之间的lcp肯定是区间最小值,然后我们可以将这个区间分成两半,算出这个lcp的贡献值,删掉,然后递归计算两个子区间就好了,不过50W的数据量,还是手写栈比较保险。

神题


     keng!

抱歉!评论已关闭.