后缀数组 专题训练

发布于 2017-12-10  4.04k 次阅读


关于后缀数组的学习,还是费了不少精力的,尤其是一开始入门,连个模板都不理解,也不会基数排序,所以这个知识点从六月一直拖到了现在,有两篇专门讲后缀数组的文章,感觉还不错,我就是看了这俩之后才算入了门,转过来:

五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码)

后缀数组应用小结

 

之后再把自己改了改的板子发上来:

 

BZOJ1717 [Usaco2006 Dec]Milk Patterns 产奶的模式

后缀数组第一题,用到了后缀数组中非常常见的分段思想。首先,如果ans可行,那么长度比ans小的也一定可行,也就是说,答案可以二分。那么,问题转化为判断存在性。height数组表示排名相邻的两个后缀的公共前缀长度,那么我们只需要判断序列中是否存在连续的一段,其height值均大于等于二分的x,且元素个数大于等于k。

 

BZOJ4698 Sdoi2008 Sandy的卡片

唉,果然还是我的语文太差,题目就是没读明白。其实,题目的意思是,定义两个串相同,当且仅当相邻元素相对大小相等。也就是说,我们只需要求出差分序列,然后答案就是这些串的LCS长度+1。

涉及到多个串的问题,套路是将多个串拼成一个,同时用两两不同的分隔符来隔断,防止发生重复匹配,之后依旧是二分答案,只需要判断连续的ht>=x的段中是否出现的n个串即可,注意边界。

 

BZOJ2754 [SCOI2012]喵星球上的点名

据说暴力可过,而且正解貌似比较复杂,所以就打的暴力(然而被COGS卡了仨点)。

直接在height上暴力扩展,不贴代码了,以后填坑吧。

 

BZOJ4556 [Tjoi2016&Heoi2016]字符串

求s[a...b]的所有字串与s[c...d]的最长公共前缀的最大值。

二分答案+主席树。首先,主席树的下标即为后缀的下标,权值就是rank[i]的数量(据说可以用别的方法建)。那么,二分出答案后,我们知道和s[c...d]最长公共前缀长度满足要求的一定是rank连续的区间,所以我们可以两次二分求出区间的左右端点,也就是说,rank在[l,r]的后缀符合要求。接着,为了保证是a...b的子串,假设我们二分的答案是x,那么就要在下标为[a,b-x+1]的范围内查询,解决了越界的问题。最后,查询时如果差分到的区间已经为0,那么可以直接返回0,作为减枝。

 

BZOJ3238 [Ahoi2013]差异

问题转化为求:

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} len(LCP(T(i),T(j)))$$

LCP的长度即为区间中height的最小值,这样,我们可以考虑每个height值对多少区间产生了贡献即可,两次单调队列,问题又转化为了一道NOIP模拟赛的题,轻松搞掉。

 

BZOJ3230 相似子串

首先求出原序列的SA,然后可以知道每个后缀产生了n-sa[i]+1-height[i]个本质不同的字串,搞成前缀和后,就可以二分排名为i的字串所处的后缀了。这样,也就可以知道排名为i的字串的左右端点了。之后,反着跑一遍SA,用ST表处理LCP就完事了。

 

BZOJ4199 [NOI2015]品酒大会

之前感觉这题可能不可做,就跳了,从成都回来以后才发现原来并没有那么难。首先,对于k相似的答案,一定对[0,k-1]相似也有贡献,所以答案只要开个全局变量不断积累即可。考虑将每个后缀按照rank排序后建成一个新的序列(因为height是rank相邻的LCP),之后将height从大到小排序后一个一个插入,那么在新序列中会形成许多区间,而两问的答案都可以直接在每个区间里搞出来。把插入一个height值看作是插入一条边,每次合并两个集合,只需考虑集合间对答案的贡献即可。并查集维护大小、最值,每次合并信息时更新答案。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974