我谔谔,我今天才学的后缀数组(之前只会后缀自动机)。
然后就想开个后缀家族大坑?
介绍
虽然说可能在各位巨佬眼里这已经是烂大街的东西了……但我现在才会(逃
思想很简单吧,对于原串的所有后缀排个序(按字典序升序),形成了一个数组(mathrm{sa}),就叫做后缀数组,方便起见定义(mathrm{rk}[i])表示(ildots n)这一段后缀在(mathrm{sa})中的排名。
然后考虑怎么求这玩意吧……
倍增排序求SA
如果直接按照定义,快排加暴力比较弄的话,(O(n^2log n))的复杂度没什么用(其实有个比较贱的方法事你可以预处理哈希然后二分比较两个后缀就匪快了)。
我们考虑采取倍增的思想,依次比较各个后缀的长度为(1,2,4,8,16,ldots)的前缀,这样的话总是可以比较出最后的结果。
更大的好处是,假如我们已经有了(2^t)下的答案,我们要对(2^{t + 1})的情况排序。那么每个后缀我们可以直接视为一个二元组((a, b)),其中(a,b)分别是(2^t)下的排名。
这样的话我们可以直接用这种思想套上快排,复杂度(O(nlog^2 n))。但观察到二元组的两元的值域都不超过(n),所以把快排改成桶排,这样复杂度就是(O(nlog n))的了。
然后更多细节参考代码吧。
SA的应用:height数组
这样看的话SA好像没啥用处?
我们定义一个(mathrm{height}[i])表示排名为(i)的后缀和他的上一名的LCP。如果你学过后缀树的话,你会发现把后缀树的叶子按照对应后缀字典序排序一下,然后这个(mathrm{height})就是每个叶子和他左侧的叶子的LCA的深度。
直接按照定义求这玩意显然复杂度(O(n^2)),难以接受。然后我们定义(h(i) = mathrm{height}[mathrm{rk}[i]]),然后我们发现有: [
h(i)geq h(i - 1) - 1
] 证明的话考虑(h(i - 1)geq 1)的情况就行了。我们假设(a = i - 1, b = mathrm{sa}[mathrm{rk}[a] - 1]),那么若(h(i - 1)geq 1),那么我们把两者截去开头一个字符还会得到两个新的后缀(a',b'),注意到有(a' = i, b' = b + 1),且(mathbf{LCP}(a',b') = h(i - 1) - 1),考虑到字典序意义上(a > b),那么显然字典序意义下也有(i > b + 1),那么说明(mathrm{rk}[i] - 1leq b + 1),因此(mathrm{sa}[mathrm{rk}[i] - 1])在排序后的后缀树中一定不会比(b + 1)离(i)更远,换言之(mathrm{sa}[mathrm{rk}[i] - 1])和(i)在树中的LCA深度(也就是串中的LCP大小)不会小于(h(i - 1) - 1)。
根据这个东西,就可以很轻松的(O(n))求出(mathrm{height})数组了。
题目
POJ 2774 Long Long Message
Description
给两个串,求两者的最长公共子串。
两个串的长度都不超过100000。
Solution
考虑把两个串强行接在一起(顺便中间加上一个特殊字符作为分隔符以防越界),那么两者的公共子串一定是某两个在分隔符两端的后缀的公共前缀,而我们要取出最长的情况。
那么我们按照(mathrm{sa})的顺序扫描所有后缀,如果出现相邻两个后缀在分隔符两侧,那就取他们的(mathrm{height})值更新答案即可。
Code
1 |
|
POJ 1743 Musical Theme
Description
给一个由([1, 88])中整数组成的数字串,要求取出两个长度相等的不重叠子串。要求:
- 两个串的长度都大于5。
- 一个子串可以通过整体加上一个整数得到另一个子串。
最大化取出子串的长度。
多组数据,串长不超过20000。
Solution
算事经典套路题了……一直知道但一直没做
首先第二个条件很鬼畜,我们考虑做一些转化搞掉它。我们直接把序列差分,这样的话除了第一项其他都能匹配(要考虑一下整个序列的第一项怎么处理啊,这个参考代码吧)。
先讲个比较逊的做法……很显然这个东西的答案具有单调性,那么考虑二分答案。
然后考虑该怎么判定答案。考虑当前二分答案为(k),然后我们对于所有(mathrm{height}[i]geq k),我们都可以合并(mathrm{sa}[i - 1])和(mathrm{sa}[i])(也就是说可能可以由这两个后缀产生答案,并且这种关系很显然具有传递性),那么就相当于除了(mathrm{height}[i] < k)的情况被“断开”了,其他地方都已经分别连在一块了。那么每一块都是可能在块内产生答案(但不可能和块外产生答案),如果说某个块中最长后缀和最短后缀的差不小于(k),那么说明该块可以取出两个不重叠的长度不小于(k)的后缀的前缀,因此(k)合法。反之(k)不合法。
这样复杂度很显然事(O(nlog n))的,可以通过此题。
然后我们考虑那个二分答案其实不需要的……我们可以用并查集来维护块。我们每个块都维护块中最长后缀和最短后缀,刚开始每个点都是自己一块。从大到小枚举所有(mathrm{height}[i])的值,然后去合并块。每次合并出新的块的时候我们判一下是否有合法答案就行了。
Code
1 |
|
POJ 3415 Common Substrings
Description
给出两个串(A,B)和一个一个正整数(k),求出两个串长度不小于(k)的公共子串的数量。
(1leq |A|,|B|leq 10^5,1leq kleqmin(|A|,|B|)),多组数据。两个串最多由全体拉丁字母组成。
Solution
首先还是考虑把(mathrm{height}[i] < k)的地方断开,剩下的地方连成块,然后剩下的每一块内部产生答案。
然后答案有两类,一类是在(A)中的后缀和排名比他小的(B)中的后缀产生答案,另一类情况是反过来的。那么会做第一类就会做第二类了。
考虑一个排名比(i)低的串,对(i)造成的贡献事两者的LCP再减(k - 1),那么我们考虑怎么去维护所有串的贡献的和。我们注意到排名比(mathrm{sa}[i])越低,和(mathrm{sa}[i])的LCP就会越来越小,从左往右事单调递增的。所以我们可以用单调栈来维护这个东西。
Code
1 |
|
LibreOJ 2059 「TJOI / HEOI2016」字符串
Description
给出一个长度为(n)的小写字母串(S),(m)询问(a, b, c, d),求出(S[aldots b])的所有子串和(S[cldots d])本身的LCP的最大值。
(1leq n, mleq 10^5, 1leq aleq bleq n, 1leq cleq dleq n)。
Solution
很显然这个东西的答案满足单调性……所以我们就二分答案吧。
那么考虑怎么判定呢。 假设当前二分出来的答案为(k),那么和后缀(cldots n)的LCP为(k)的后缀在后缀数组中一定为一段区间(假设为([l, r])),那么如果这段区间里有个(i)满足(mathrm{sa}[i]in[a, b - k + 1]),那么显然答案合法,反之则不合法。
于是我们队后缀数组建主席树,然后每次判定就是确定([l, r])(这个也可以二分答案搞)之后在一段区间里查询是否有值在一段区间里的位置就行了。
Code
1 |
|
后缀自动机
介绍
还在路上,马上就来了(鸽并感)
题目
例题1
Description
给一个字母串,求出它的最小表示法(就是可以进行若干次循环位移,使得串的字典序尽可能小)。
(nleq 10^{5})。
Solution
把串复制两份接一块,那么很显然就是要求新串的一个长度为(n)的子串,使得这个串的字典序最小。
那么考虑建新串的后缀自动机。从根开始每一步走尽可能小的转移边即可。
LibreOJ 2033 「SDOI2016」生成魔咒
Description
有一个初始为空的整数串(S),要求动态的往尾部加数,每次操作完后求数字串的本质不同子串数目。
操作次数不超过十万次,(S)中的数在([1, 10^9])中。
Solution
SPOJ NSUBSTR
Description
给一个字符串(S),用(F(x))表示所有(S)的长度为(x)的子串中出现次数的最大值。求(F(1)ldots F(|S|))。
(|S|leq 250000)。
Solution
SPOJ LCS2
Description
给你至多十个串,求他们的最长公共子串。
每个串的大小不超过十万。
Solution
LibreOJ 2102 「TJOI2015」弦论
Description
对于一个长为(n)的小写字母串(S),求它的第(k)小子串。
每组数据还给定一个(T),表示对于不同位置的相同子串是否算一种。
(nleq 5times 10^5, kleq 10^9)。
Solution
LibreOJ 2137 「ZJOI2015」诸神眷顾的幻想乡
Description
给出一个点上写着字符(这里字符定义为小于(c)的自然数)的树,度数为1的点的数量不超过20。定义其子串为从一个点延最短路走到另一个点(显然方案唯一),把经过的点上的字符顺次写下来所得到的字符串。
求这棵树有多少种本质不同子串。
(1leq nleq 10^5, 1leq cleq 10)。
近期评论