重写平方串,润和琳墩串

/dk

Posted by ShanLunjiaJian's Blog on September 7, 2022

做xix open cup遇到了两个平方串题。再写一写,可能这次会比较深刻吧。


square(tandem repetition, repetition, repeat)

定义一个串是平方串,当且仅当它的前一半和后一半相同。它的前一半称作它的平方根或简称根。

类似地可以定义立方串,四次方串……但是它们意义不是很大。


boi2004 repeats

求一个串的子串的最高次数,并输出所有具有这一次数的子串。

给出一个求所有重串的做法。从大到小枚举根的长度\(l\),然后按\(l\)大小分块,那么根一定是一个块前缀和一个块后缀。用sa求出相邻两块的lcp和lcs,然后就得到一个区间的重串,这里还是画一下吧 :

img

然后为了求出连续重复次数,我们可以直接在这个上面尝试继续扩展,也就是把相同的块直接连起来,在两边尝试上面的东西。写起来并不困难。


noi2016 优秀的拆分

求所有子串划分成形如AABB的串的方案数之和。

我们枚举一个拆分,也就是枚举两个相邻的重串这样的,那么问题是求出每个位置作为开头和结尾的重串数量。套用上个题的做法即可。


zjoi2020 字符串

求区间平方串个数。

长\(2k\)的平方串贡献一个矩形,长\(2k\)的一个平方串区间贡献一串矩形。这是一个经典问题,我们拿两条斜线容斥一下就好了,具体见command_block在洛谷的题解。所以转化成平行于\(x=y\)的斜线加,右下2-side矩形求和,发现左下2-side矩形比较好做,分开考虑包含的和经过边界的斜线即可。复杂度\(O(n\log^2 n)\)。


xix open cup, gp of gomel C. Three Indices

用若干个区间和长度表示所有允许\(1\)的汉明距离的平方串,具体地,允许左右两边最多一次出现对应位置不同。

这个被称为 approximate tandem repeatition。

考虑一个允许\(1\)的汉明距离的sa,我们求一个lcp,跳过一个不同字符,然后再求一个lcp即可。统计答案的时候,枚举两边有多少不同的卷起来即可。

可以扩展到允许\(k\)的距离,复杂度将是\(O(nk\log n)\)。


run

注意到上面的方法说明相同长度的平方串形成若干个区间。定义一个run(译名好像是 顶天立地串/kx)是一个周期\(p\)和极长的以这一周期作为最小周期的子串\([l,r]\)组成的二元组(但是我会记为\((l,r,p)\)),显然它表示了一堆平方串。定义一个串的runs是它的所有run的集合。

The runs theorem 一个串中run的个数不超过\(n\)。

定义一个run的根是它里面任意一个长\(p\)的子串。如果我们找到了一个run的一个根,那么可以向两边爆力扩展,下面的结论说明了这样做的复杂度 :

The runs theorem 定义一个run的指数是\(\frac{r-l+1}{p}\)。一个串中run的指数和不超过\(3n-3\)。

但是一般我们不会这么做,因为一次lcp一次lcs就可以实现向两边扩展了。

如果我们求出了所有run,那么很容易枚举所有平方串。枚举一个长度\(2kp\)即可。


lyndon word

接下来我们描述lyndon word的理论。

一个串是lyndon串,当且仅当它比所有非平凡后缀都小,或者说它是所有循环同构中严格最小的。按照定义,aaaaa不是lyndon串,但是a是。

接下来我们考虑lyndon串的结构。

显然 如果lyndon串\(w=uv\),那么\(u<v\)。

定理1 一个串\(w\)是lyndon串,当且仅当它是单字符,或者它可以分解成两个lyndon串\(w=uv\),其中\(u<v\)。

证明 \(\Leftarrow\) : 考虑所有后缀。

\(\Rightarrow\) : 找到\(w\)的最小真后缀,那么根据定义它是lyndon串,直接令它为\(v\),剩下的部分为\(u\)。接下来证明\(u\)是lyndon串,考虑\(w\)比\(w\)的任意后缀小,而\(u\)比\(w\)小,所以\(u\)比\(w\)的任意后缀小,而\(v\)是\(w\)的最小真后缀,在\(w\)的一个后缀中把\(v\)替换成空对大小不会有影响,而把\(v\)替换成空就变成了\(u\)的后缀,所以\(u\)比\(u\)的任意后缀小。

定义一个lyndon串的标准分解是最小真后缀和剩下的部分。分解形成一棵树,可以猜到这是它的sa的笛卡尔树。


lyndon root

显然由于run的周期是最小周期,我们知道每个run必有一个lyndon串作为它的根,称为lyndon根。接下来我们指出lyndon根的重要性质。

引理1 设\(w=u^ku^\prime a\),其中\(u\)是lyndon串,\(a\)是一个字符,\(u^\prime\)是\(u\)的极长前缀(可能为空),也就是向后加入\(a\)的话则不再是\(u\)的前缀。设\(u\)中\(u^\prime\)之后的字符是\(c=u_{\vert u^\prime\vert+1}\)。则

  • 如果\(a>c\),那么\(w\)是一个lyndon串。

  • 如果\(a<c\),那么以\(w\)为前缀的串的最长lyndon前缀必然是\(u\)。

证明 很直接。

  • 如果\(a>c\),那么显然。

  • 如果\(a<c\),那么显然。

反复阅读你就懂了(

所以我们知道,从左往右扫原串,如果遇到了case 2,那么这个run的lyndon根必然是原串一个后缀的最长lyndon前缀,这个数组称为lyndon数组,而我们马上会描述求这个东西。为了稳定遇到case 2,我们可以把字典序反过来再做一遍,这样正序和反序下的lyndon array必然有一个给出了lyndon根(,实际上,容易发现另一个总是给出长\(1\)的平凡lyndon串,所以实现起来更为简单了)。这实在是比较的离奇。


lyndon分解, lyndon array

定义一个串的lyndon分解是极小的划分成若干lyndon串的方案。根据定理1,极小当且仅当这些lyndon串是从大到小排列的。容易证明lyndon分解唯一,这说明我们可以按照定理1以任意顺序尽可能合并得到lyndon分解。

定理2 lyndon分解的第一部分是最长lyndon前缀,最后一部分是最长lyndon后缀。

证明 如果不是最长的,根据lyndon分解唯一,我们知道必然还可以合并。

为了求lyndon数组,我们可以考虑从右往左扫,维护当前后缀的一个极小lyndon串分解。接下来我们会加入一个字符,然后我们不断尝试把这个字符和右边合并,还是根据定理1我们知道合并只需要比较两个lyndon子串的字典序,比较后缀的字典序即可。最多会进行\(n-1\)次合并,所以我们可以使用二分hash做到\(O(n\log n)\),或者sais 四毛子rmq做到\(O(n)\)。

所以我们现在已经会\(O(n)\)算runs了!

二分hash做法的实现收录在我的 板子/Lyndon Array。


本原平方串,三平方串定理(three squares lemma)

定义一个平方串是本原平方串,当且仅当长度的一半是它的最小周期。

三平方串定理 如果三个本原平方串\(uu,vv,ww\),满足\(uu\)是\(vv\)的真后缀,\(vv\)是\(ww\)的真后缀,那么\(\vert u\vert+\vert v\vert\leq\vert w\vert\)。

所以我们知道本原平方串有\(O(n\log n)\)个。一种称为fib字符串的串达到了这个上界,具体可以看oi-wiki的main-lorentz词条。

定理3 对于所有run \((l,r,p)\),其\(r-l-2p\)的和为\(O(n\log n)\)。

证明 一个run中所有长\(2p\)的子串就是所有的本原平方串,其数量为\(r-l-2p+2\),而本原平方串的数量是\(O(n\log n)\)。


接下来是更多关于lyndon串的东西,而和runs关系不大了。

求出一个lyndon分解

duval’s algorithm

根据引理1,我们可以简单地增量求lyndon分解。直接从左往右扫,维护\(u,k,u^\prime\)即可,尝试匹配\(u\),如果不匹配,如果是case 1则\(u:=u^\prime,k:=1\),否则\(u:=\varnothing\)之类的。但是这个做法不能求每个前缀的lyndon分解,需要在串最后加入一个结束符。

sa

刚才在定理1的证明中,我们断言把最小后缀替换成空不影响前面的大小关系,所以可以直接后缀排序,每次选择剩下的部分中的最小后缀,可以知道最后我们选择了sa的前缀\(\min\)。但是这个做法难以对每个后缀求lyndon分解。可能其实居然有点用吧。


jsoi2019 节日庆典

求每个前缀的最小表示。\(n\leq 3\times 10^6\)。

lyndon分解的最后一部分是最小后缀,但是这里是最小表示而不是最小后缀,所以我们要考虑往后接了一个原串之后谁的字典序更小。考虑duval,发现如果我们知道了\(u^\prime\)的lyndon分解就赢了,因为\(u^\prime\)比前面任何后缀都要小,那么我们就直接递归到\(u^\prime\),注意到\(u^\prime\)的长度不超过原串的一半,所以我们同时维护\(\log\)个duval即可。比较两个可能成为答案的后缀,发现如果短的不是长的的前缀,那么由于你在duval,显然是长的更优,如果短的是长的的前缀,画一画发现转化成比较一个后缀和原串,z algo即可。复杂度\(O(n\log n)\)。

这个东西看起来很有趣。发现duval维护的是一个不一定是lyndon分解的最后一部分的东西,它不一定是因为后面可能加入各种字符。这一递归说明这样的东西可能很少,于是我们干脆导出significant suffix,尝试更深刻地描述这些东西的结构。


significant suffix

定义一个串\(s\)的significant suffix,是它接上某一个串之后可能的在\(1,...,\vert s\vert\)中最小的后缀,也就是认为空字符和任何字符不可比,则两两不可比的最小后缀集合,也就是接下来可能作为lyndon分解的最后一部分的位置,看起来似乎也就是duval算法中维护的\(u^ku^\prime\)和对\(u^\prime\)不断递归duval再得到的\(u^ku^\prime\)们。

显然对于任意两个significant suffix,短的是长的的前缀。

定理4 长度相邻的significant suffix \(u,v\),其中\(\vert u\vert>\vert v\vert\),则\(\vert u\vert\geq 2\vert v\vert\)。

证明 不使用引理1来证明它。我们知道,\(u,v\)要么前\(\vert u\vert-\vert v\vert\)个字符相同,要么\(v\)没有这么长。继续推可以知道它们都以\(\vert u\vert-\vert v\vert\)作为周期。设这个周期是\(p\),那么如果\(v\)不完整包含\(p\),显然满足\(\vert u\vert>\vert v\vert\),则\(\vert u\vert\geq 2\vert v\vert\);否则我们知道\(u=ppw,v=pw\),其中\(w\)是某个串。此时由于\(v\)是significant suffix,存在一个\(x\)满足\(pwx<ppwx\)。但是这推出\(wx<pwx\),所以此时\(v\)不是最小后缀,\(w\)比它更小,矛盾了。


jsoi2019 节日庆典

直接尝试维护所有的significant suffix。由于两个significant suffix,短的必然是长的的前缀,所以每次加入一个字符的时候,只需要比较两个字符,求答案和前面那个做法是一样的。


zjoi2017 字符串

区间加,求区间最小后缀。\(n\leq 2\times 10^5,q\leq 3\times 10^4\)。

我们直接在线段树上维护significant suffix。直接保留右儿子所有significant suffix,虽然其中可能有不是significant suffix的串,我们只需要让信息在\(O(\log n)\)即可;左儿子最多有一个串是significant的,我们比较接上右儿子之后哪个最小,如果仍然存在忽略空字符不可比的,根据定理3的证明应该保留其中最长的那个。使用二分hash支持比较两个串,比较的时候需要\(O(\log^2 n)\),复杂度\(O(\log^4 n)\)。可以考虑用类似于多树二分的trick。

为了让它跑的快一点,注意到我们有\(q\log^2 n\)次比较两个串和\(q\)次修改,所以考虑改用根号平衡维护hash值,就可以\(O(\sqrt{n})-O(1)\)了。总复杂度\(O(n\log^2 n+q\log^3 n+q\sqrt{n})\)。