序列问题

Published: June 14, 2019 by Daltao

Categories:
problems 4

字符串的一些周期、border性质
字符串的一些等口胡性质
回文的一些性质
一些回文题目
回文的最小分解
Z algorithm
后缀树
最大表示法
惩罚函数与序列匹配问题
字典序最小子序列
判断A是否是B的子串
本质不同的子串数目
最短的非子串
一些子串查询问题
一些自动机
- KMP自动机
- AC自动机
- 后缀自动机
  - 区间本质不同子串数
- 回文自动机
字符串排序
子串的比较
汉明距离小于$k$的子串查找
后缀平衡树
串联重复（Tandem repeats）
最小字典序拼接字符串
参考资料

字符串的一些周期、border性质

对于字符串$s=s_0s_1\ldots s_{n-1}$，记$s(i..j)$表示字符串$s_is_{i+1}\ldots s_j$，记$pre(s,l)$表示$s(0..l-1)$，$suf(s,l)$表示$s(n-l..n-1)$。

如果存在整数$p$，满足$\forall i+p<n$，有$s_{p+i}=s_{i}$，那么称$p$是$s$的一个周期。

如果存在整数$b$，满足$pre(s,b)=suf(s,b)$，那么称$b$是$s$的一个border。

弱周期定理：若$p$和$q$都是字符串$s$的周期，且$p+q\leq |s|$，那么$gcd(p,q)$也是字符串$s$的周期

命题1：若字符串$u$、$v$满足$2|u|\geq |v|$，则$u$在$v$中的所有匹配位置形成一个等差数列。

命题2：若字符串$u$、$v$满足$2|u|\geq |v|$，且$u$在$v$中有两个以上匹配位置，则形成的等差数列的公差为$u$的最小周期$per(u)$

命题3：字符串$s$的所有border按长度排序后可以分成$O(\log_2|s|)$段，每一段都是一个等差数列。

字符串的一些等口胡性质

以下内容仅经过个人简单证明，主要用于切题，实属口胡。

定义1：对于字符串$S$，如果存在某个前缀$P$，从$S$中删除前缀$P$并将$P$追加到结果后面，得到字符串$S'$，如果$S=S'$，那么称$\mid P\mid$是$S$的一个旋转周期。

比如对于$abab$，我们可以发现其拥有旋转周期$2$，因为$(ab)ab+ab=abab$。

命题1.1：字符串的旋转周期一定是字符串的周期

证明：

实际上旋转周期是字符串周期的一个子集。

命题1.2：如果$a$是字符串$S$的旋转周期，那么$\mid S\mid-a$也是$S$的一个旋转周期。

证明：

我们将$S$分解为两部分$A+B$，其中$A$的长度为$a$。那么我们发现$A+B=B+A=S$，这意味着将$B$移动到尾部得到的也是$S$，因此命题得证。

命题1.3：如果$a,b$是字符串$S$的旋转周期，那么$gcd(a,b)$也是$S$的一个旋转周期

证明：

不妨认为$a\lt b$，那么在旋转$a$后我们得到了相同的字符串$S$，而再旋转$b-a$一定能得到相同的字符串$S$。因此我们得出了$b-a$也是$S$的一个旋转周期。

利用辗转法可以得出$gcd(a,b)$是$S$的一个旋转周期。

命题1.4：长度为$n$的字符串$S$的最小旋转周期$p$，一个数$x$是$S$的旋转周期当且仅当$p\mid x$。

证明：

不妨设所有旋转周期的集合为$G$，求出$G$中所有数的最大公约数，就能得出最小旋转周期$p$。因此$p$一定是所有旋转周期的因子，同时$p$的任意倍数也一定是一个旋转周期。

用这个性质，我们可以通过枚举$p$的因子得到$S$的最小旋转周期，时间复杂度为$O(n\log_2n)$（通过删除素因子的优化）。

命题1.5：长度为$n$的字符串$S$的最小旋转周期$p$一定满足$p|n$。

由命题1.4和长度n是$S$的一个旋转周期可以直接得出。

定义2：对于回文$S$，如果存在某个前缀$P$，从$S$中删除前缀$P$并将$P$追加到结果后面，得到字符串$S'$，如果$S'$还是回文，那么称$\mid P\mid$是$S$的一个回文旋转周期。

命题2.1：字符串的旋转周期一定是回文旋转周期

证明：

略。

命题2.2：对于回文$S$的最小回文选择周期$p$，一定满足$p\mid |S|$。

证明：

假设最小周期不能整除回文$s$，则记录$r=|S| \pmod p$，记录$a=S(0..r-1)$，记录$b=S(r..p-1)$，则回文$S=abab\ldots aba$。

考虑到$p$是$S$的回文旋转周期，因此$abab\ldots aab$也是回文，即$ab=(ab)^T$，这里$x^T$表示将字符串$x$前后翻转。同时由于$S$是回文，可以得到$ab=(ba)^T$，总结可以得出$ab=ba$。之后我们考虑周期$r$，可以发现$baba\ldots abaa=abab\ldots aba=S$，即$r$也是$S$的回文旋转周期，这和$p$是最小回文旋转周期相悖。

命题2.3：如果$a,b$均为回文的回文旋转周期，则$gcd(a,b)$也是回文的旋转周期。

证明：

口胡。暂时没有能力证明。

命题2.4：长度为$n$的回文$S$的字符串最小旋转周期为$p$，如果$p$是奇数，那么$S$的最小回文旋转周期为$p$，否则$p$为偶数，$S$的最小回文旋转周期为$\frac{p}{2}$

证明：

口胡。暂时没有能力证明。

定义3：对于一个字符串$S$，称$k$为字符串的周期，当且仅当对于任意有意义的$i$和$i+k$，都有$S_i=S_{i+k}$。

命题3.1：如果$k$为字符串$S$的周期，当且仅当$S_i=S_{i\pmod k}$。

回文的一些性质

命题1：回文的border也是回文。

命题2：字符串A的所有偶数长度回文前缀中，最短的回文前缀长度记作x，次短的回文前缀长度记作y，一定有$2x\leq y$成立。

如果不然，则有$2x>y$，则可以证明$2x-y<x$一定也是偶数长度的回文前缀，这与x是最短的前缀相悖，因此命题一定成立。

提供一道题目。

一些回文题目

题目1：对于由$1$到$k$的数值组成的长度为$n$的序列，如果能通过旋转操作（将某个前缀移动到字符串尾部）将其变成回文，那么这样的序列称为特殊的。问总共有多少不同的特殊序列，结果对某个素数$p$取模。

我们可以通过统计所有满足条件的回文的最小回文旋转周期的和即可得到我们想要的结果。

我们可以枚举最小旋转周期$x$，计算最小旋转周期$x$对应的回文数目。我们知道以$x$作为旋转周期的回文有$k^{\lceil x/2\rceil}$个，而最小旋转周期为$x$的回文可以通过容斥技术计算得到。时间复杂度为$O(D^2)$，其中$D$是$n$的因子数目。

现在认为最小旋转周期为$x$的回文有$c_x$个：如果$x$是偶数，那么它对结果的贡献应该为$\frac{1}{2}\cdot x\cdot c_x$。如果$x$是奇数，那么它对结果的贡献为$x\cdot c_x$。

提供一道Atcoder的题目。

题目2：给定一段长度为$n$的序列$a_1,\ldots,a_n$，要求计算它的子序列能形成多少不同的回文（空序列也是回文），结果模上素数$p$。其中$1\leq n\leq 2\times 10^3$，且$a$中仅包含小写字母。

这个问题可以通过区间DP+贪心来做。记$dp(l,r)$表示$a_l,a_{l+1},\ldots,a_r$能形成多少不同的回文。但是之后我们枚举最两端的字符即可。时间复杂度为$O(26n+13n^2)$。

题目3：给定一段长度为$n$的序列$a_1,\ldots,a_n$，要求计算有多少子序列是回文（空序列也是回文），结果模上素数$p$。其中$1\leq n\leq 2\times 10^3$，且$a$中仅包含小写字母。

这个问题也还是一个简单的区间DP。记$dp(l,r)$表示$a_l,a_{l+1},\ldots,a_r$中包含多少不同的回文子串。但是这里有一个问题，我们可以枚举左右是否匹配来计算某个状态，这时候$dp(l,r)=dp(l+1,r)+dp(l,r-1)+dp(l-1,r-1)(1+[a_l\equiv a_r])$。但是这里会存在一个重复统计的情况，$dp(l+1,r)$与$dp(l,r-1)$都包含了$dp(l-1,r-1)$的情况。

我们这边可以用一种非常简单的技术进行去重。我们定义$dp(l,r,k)$，其中$k=1$表示当前可以修改的是$r$，当$k=0$的时候表示当前可以修改的是$l$。则$dp(l,r,1)=dp(l,r-1,1)+dp(l,r,0)$，而$dp(l,r,0)=dp(l-1,r,0)+[a_l\equiv a_r]dp(l+1,r-1,1)$。可以发现这时候统计的是没有重复的。总的时间复杂度为$O(2n^2)$。

题目4：将一段长度为$n$的序列$a_1,\ldots,a_n$重复拼接$m$次，要求计算有多少子序列是回文（空序列也是回文），结果模上素数$p$，其中$1\leq n\leq 50$，$1\leq m\leq 10^{18}$，且$a$中仅包含小写字母。

我们可以记$dp(i,j,1)$表示$a_j,\ldots,a_n (i\times a)$中有多少回文子串，且下一个移动的是右端，而$dp(i,j,0)$表示$(i\times a)a_1,\ldots,a_j$中有多少回文子串，且下一个移动的是左端。

可以发现$dp(i,?,?)=Adp(i-1,?,?)$，即可以通过前一个状态通过线性变换得到，其中$A$的大小为$2n\times 2n$，其中$dp(0,?,?)$需要特殊计算。我们可以通过BM算法直接暴力计算前面几项，之后插出线性递推公式。通过一些多项式理论可以做到$O(8n^3+4n^2\log_2n)$，还是很快的。

题目5：给定一颗拥有$n$个顶点的有根树，每个顶点上都有一个字符。令$s(u)$表示根顶点到顶点$u$路径上顶点字符的拼接得到的字符串，记$f(x)$表示字符串$x$中出现的最长回文子串的长度。现在要求对于顶点$i=1,\ldots,n$，计算$f(s(i))$并输出。其中$1\leq n\leq 10^6$，字符仅包含小写字母。

提供一道问题。

假设我们从父顶点$u$移动到它的子顶点$v$，这时候考虑$f(s(v))$与$f(s(u))$的区别，可以发现一定有$f(s(v))\geq f(s(u))$，且如果$f(s(v))>f(s(u))$的话，最长回文唯一且一定以$v$结束，事实上，由于$f(s(v))\leq f(s(u))+2$，因此在这种情况下，仅有两种可能性：$f(s(v))=f(s(u))+1$或$f(s(v))=f(s(u))+2$。

换言之我们只需要检测两种情况即可。由于我们可以通过哈希来高效的判断回文，这样我们只需要比较两边的哈希值。但是这里有个问题，就是我们的哈希是动态修改的，因此需要借助BIT等数据结构来维护哈希，这样做的时间复杂度为$O(n\log_2n)$。考虑到哈希由于取模操作已经效率低下了，这样一合并常数会更加大。

我们可以类似莫队算法的方式维护一个全局$l,r$指针，指示当前的哈希范围，可以发现每次顶点间的移动，$l,r$指针的变动都是$O(1)$的。我们可以用一个双端队列来维护扫描范围内的哈希值，这样时间复杂就可以优化到$O(n)$。

题目6：给定一个空字符串$S$，之后执行$n$次操作。操作分三类：

向$S$尾部插入一个字符$c_i$
向$S$头部插入一个字符$c_i$
撤销上一个插入操作

要求每次操作完成后，输出$S$中的最大回文长度。其中$1\leq n\leq 10^6$。

这道题目和题目5类似，只不过支持前端插入而已。而支持前端插入也非常简单，为字符串的前缀也维护两个滚动哈希即可。总的时间复杂度为$O(n)$。

回文的最小分解

题目1：字符串$S$的最小回文分解

参考https://arxiv.org/pdf/1506.04862.pdf。

时间复杂度为$O(|S|\log |S|)$。

一些题目：

题目2：给定字符串$A$和字符串$B$，你每次操作可以选择$B$的某个区间，反转区间中的元素（第一个变成最后一个）。问至少需要多少次操作，才能将$B$转换成$A$。

原题。

首先我们创建一个新的字符串$C=A_1B_1A_2B_2\ldots A_nB_n$。

问题等价于找到$C$的一个划分$P_1,\ldots,P_k$，其中$P_i$为一个回文或者双重字符串，即$P_i=a_1b_1a_2b_2\ldots a_tb_t$，其中$\forall j(a_j=b_j)$。

我们希望我们的划分中非双重字符串的回文数量最少，因为没给回文串都需要一次翻转操作。

可以参考最小回文划分的方式，时间复杂度为$O(n\log n)$。

题目3：给定子符串$S$，要求将$S$划分为若干个非回文字符串，要求找到最小划分数和最大划分数，或报告无解。

提供一道题目。

定义$P$表示所有回文构成的集合。

首先我们要理解在解决最小回文划分过程中对于回文$p$，我们定义的series_link和link以及diff：

link表示回文的最大border
diff表示最大回文与最大border的长度差，即$|p|-|link(p)|$
series_link表示沿着link向上找到的第一个border $x$，满足$diff(p)\neq diff(x)$。

而我们是怎么实现最小回文划分的，我们定义$dp(i)$表示$S[0\ldots i]$的最小回文划分数，我们的dp转移类似于

\[dp(i)=1+\min_{j<i\land S[j+1\ldots i]\in P} dp(j)\]

当然这个转移是$O(|S|^2)$的，但是可以借助所有border只能形成$O(\log |S|)$段diff的等差数列这个性质来进行优化。

具体就是我们定义一个mem数组，其中$mem(v)$表示回文$v$的所有border中与$v$在同一个等差数列的border序列$v_1,\ldots,v_k$的dp值的最小值，即

\[mem(v)=\min_{u\in border(v)\land diff(u)=diff(v)} dp(n-len(u))\]

其中$n$表示目前在计算的是$dp(n)$。

伪代码如下

get_mem(v) {
   mem[v] = dp(n - (series_link(v) + diff(v)));
   if(diff(v) == diff(link(v))) {
      mem[v] = min(mem[v], mem[link(v)]);
   }
   return mem[v];
}

for(n = 0;; n < S.size(); n = n + 1) {
   dp[n] = inf;
   for(border = max_suf(n); border != NULL; border = link(border)) {
      dp[n] = min(dp[n], get_mem(border) + 1);
   }
}

可以发现我们只要修改mem的定义，就可以解决这个问题

\[mem(v)=\min_{i>len(series\_link(v))\land i<len(v)\land S[n-i+1\ldots n]\notin P} dp(n-i)\]

我们计算每个dp点都只要查询$\log S$次区间最小值，利用线段树，我们可以做到$O(S(\log S)^2)$的时间复杂度。

Z algorithm

最近做了这道题，一开始直接用哈希+二分来比较大数，这样时间复杂度为$O(n\log_2n)$，但是java死活跑不过去。之后发现可以通过LCP来快速定位不同的字符出现位置来加速比较，于是用了SAIS线性处理LCP，终于在900+ms内跑过了。

看了下正解，好像用的是Z algorithm，之前听过但是一直没学，所以现在补一下。

Z algorithm用于在给定的序列$S[1..n]$上建立一个Z函数，其中$Z(i)$表示字符串$S[1..n]$和字符串$S[i..n]$的最长公共前缀长度。

下面我们来考虑如何实现线性时间处理Z函数。对于每个$i$，我们始终维护一个区间$[l,r]$，区间满足$r$最大，且$l\leq i\leq r$，且$S[l..r]$是$S[1..n]$的前缀。

我们始终设置$Z(1)=n$。接下来我们计算$Z(2),\ldots, Z(n)$。假设我们处理完了$i-1$后，接下来开始处理$i$。有几种情况：

如果此时$i=2$，那么我们就设置$l=i$，暴力计算$r$。
如果此时$r<i$，这说明不存在左边界小于$i$的包含$i$的区间（假如存在，那么就我们在处理$i-1$的时候就会有$r\geq i$）。因此我们重新设置$l=i$，并暴力计算$r$。
此时一定有$l\leq i\leq r$。我们记$t=i-l+1$,记录$k=r-i+1$，那么我们可以保证$Z(i)\geq min(Z(t), k)$，因为$S[i..n]$与$S[t..n]$的最长公共前缀长度为$k$。下面我们继续分两种情况讨论：
1. 如果$Z(t)>k$，那么此时一定有$Z(i)=k$，且$l$和$r$不变。
2. 否则$Z(t)\leq k$，我们可以保证$Z(i)\geq k$，这时候我们可以将$l$设置为$i$，$r$向右暴力扩展。

除了暴力操作部分，其余的操作时间复杂度都是$O(n)$。并且容易发现每次暴力操作都会使得$r$增大，而$r$只会在$i$增大时减少1，因此暴力最多发生$O(2n)$次。总的时间复杂度为$O(n)$

换了Z algorithm后，233ms就通过了。

题目1：给定一个长度为$n$的字符串$s$，定义$f(i)$表示字符串$s[0..i]$中有多少后缀与前缀相同，且后缀的长度不超过$\lfloor\frac{i+1}{2}\rfloor$。

会发现kmp适合用于求最大border，但是不适合求满足奇奇怪怪的border数目，而z函数非常适合统计border数，尤其是满足奇奇怪怪的border数目。

后缀树

很早以前了解到后缀树算法，但是一直不会。本来以为会后缀自动机就不需要学后缀树，但是，后缀自动机的各种定义太过复杂，已经忘光了，最近做到一道印度人出的题，似乎要用到后缀自动机比较高级的功能，但是不会，但是假如是后缀树的话，由于是树状结构，因此是可以搞的，所以去学了下。

学习的资料：斯坦福大学课件，stackoverflow大佬讲解。

这里简单讲一下后缀树的特点。我们可以考虑将长度为$n$的某个序列的所有后缀插入到一株前缀树中，最后得到的就是后缀树。但是与前缀树不同的是，在前缀树中顶点代表一个字符，而后缀树中边代表一个字符。但是这样做可能会出现$O(n^2)$个顶点，于是我们可以将那些只有一个子结点的顶点与子顶点压缩成一个顶点，这样一条边就代表了某个连续子序列。由于每个后缀最后一定肯定是不同的顶点，因此会有$n$个顶点，之后每次合并都会使$n$个顶点中两个不连通的顶点连通，因此会合并$n-1$次，总的顶点数为$2n-1$。

上面的图引自wiki，大家看一下就好了。

至于代码是不可能有的，根本不会，我用的也是别人写的库。

问题1：给定一个字符串S，和$m$个查询，每个查询给定$l,r,X$，要求找出所有$S[l..r]$的所有字典序严格大于X的子串中最小的

这是cf的原题。

一开始的想法是实现一个在线维护后缀的数据结构，但是好像不存在这种东西。于是就转向后缀树，希望能树上维护减少难度。

我的做法是这样的，首先建立S的后缀树，之后我们在后缀树上DFS，给每个叶子分配ID，且要求每个顶点子树中叶子的ID是连续的，这样我们就可以将每个顶点表示成一个区间，然后丢到线段树上进行维护。

之后我们将查询按$l$从大到小进行处理，当处理到某个$l$的时候，我们就将所有$ID$大于等于$l$的叶子激活。之后在后缀树上找到$X$对应的顶点，之后向上回溯，寻找S中是否有个较大的子串满足$r-query(L,R)+1>depth$，其中$query(L,R)$表示的是查询当且顶点子树下已经激活的ID最小的叶子的ID。

整个算法的运行时间是$O(26n+26M\log_2n)$，其中$M$是所有$X$的长度总和。

可以发现把问题丢到树上就非常容易解决。

最大表示法

考虑给定一个循环序列$s_0,s_1,\ldots,s_{n-1}$。这里我们定义循环字符串$S_i$，其第$j$个字符为$s_{i+j\pmod n}$，长度为无限。这里存在共$n$个不同的起始位置以及对应的$n$个不同的循环字符串。

现在我们希望求解这$n$个循环串中字典序最大的那个。

一个简单的思路就是直接利用倍增+基数排序，可以做到$O(n\log_2n)$时间复杂度内求解。

但是有一种很精妙的线性算法存在，可以求解上述问题。

我们始终维护当前找到的字典序最大的循环串（实际上只需要维护起始坐标即可），之后不断尝试所有其它的起始位置。比较两个子串的方式就是暴力比较，但是这里有一个技巧，当我们通过比较发现$S_i$和$S_j$的最长公共前缀长度为$k$的时候，且$S_i$的第$k+1$个字符比$S_j$的大。这里我们可以直接断言，对于任意$0\leq t\leq k+1$，$j+t$一定不可能是最大循环串的的起始下标，因为其一定比以$i+t$作为起始坐标的循环串小。

利用这个性质以及双指针技术，我们会发现每次暴力比较的时候，每次比较都会将左右指针中的一个右移一位，而每个指针最多右移$n$次，因此暴力比较部分时间复杂度被约束在$O(n)$。而总的时间复杂度实际上也是$O(n)$。

惩罚函数与序列匹配问题

一般的序列匹配问题就是给定一个模式串$P$和一个字符串$S$，要求找到所有的$S$中与$P$相同的子串的起始坐标。这一类问题已经被KMP，哈希，自动机等算法按在地上摩擦了。

但是除了这些算法外，FFT也可以解决序列匹配问题。

我们记$m$为$S$的长度，$n$为$P$的长度。

我们先定义一个惩罚函数$C(i,j)=S(i)-P(j)$。之后对于某个给定的$S$中的起始下标，我们可以定义一个匹配函数$M(t)=\sum_{i=0}^{n-1}C(i+t,i)$。我们希望如果某个起始下标为$t$的$S$子串与$P$匹配，那么$M(t)=0$。

上面的定义确实能保证匹配的时候$M(t)=0$，但是不匹配的时候也是可能等于$0$的，比如$S=ab,P=ba$。这是因为惩罚函数的值可能是负数。因此一个好的距离函数应该满足$C(i,j)=0$当且仅当字符$S(i)$和$P(j)$可以匹配，其余时候都应该是正数。

于是乎一个简单的修改就是定义$C(i,j)=|S(i)-P(j)|$，现在的距离函数是正确的，但是却堵死了我们优化的门路。我们可以换一个定义：$C(i,j)=(S(i)-P(j))^2$，这也是一个好的惩罚函数的定义，但是它是可以通过FFT进行加速的。

考虑到

\[\begin{aligned} M(t)=&\sum_{i=0}^{n-1}C(i+t,i)\\ =&\sum_{i=0}^{n-1}(S(i+t)^2+P(i)^2-S(i+t)P(i))\\ =&\sum_{i=0}^{n-1}S(i+t)^2+\sum_{i=0}^{n-1}P(i)^2-\sum_{i=0}^{n-1}S(i+t)P(i) \end{aligned}\]

其中前两项都是前缀和，这个很好预处理。考虑最后一项$\sum_{i=0}^{n-1}S(i+t)P(i)$，它实际上是$S$与$P$的等差卷积中$x^t$的系数。我们可以利用快速傅里叶变换在$O(m\log_2m)$求解。

当然讲了这么多，甚至用上了重武器FFT，才能达到$O(m\log_2m)$的时间复杂度求所有起始位置，远不如线性时间复杂度的KMP和哈希。那我们为啥要学它呢？

因为用惩罚函数的方式，我们可以非常灵活的定义惩罚函数，从而计算所有匹配子串。

考虑下面几个例子：

例子1：给定长度为$n$的模式串$P$和一个字符串$S$，要求找到$P$在$S$中所有出现位置的起始下标。这里特殊的是$P$和$S$中可能存在通配符$?$，它可以匹配任意一个字符。比如$?ab$与$a?b$是匹配的。这里$n\leq m\leq 10^5$。

很显然这里KMP和哈希都是无法使用的。但是我们还是可以用惩罚函数的方式。

首先我们定义通配符$?$的值为$0$，且定义$C(i,j)=(S(i)-P(j))^2S(i)P(j)$。那么$C(i,j)$始终非负，且$0$仅在$S(i)$与$S(j)$可以匹配的时候取到。

下面我们来展开公式：

\[\begin{aligned} M(t)=&\sum_{i=0}^{n-1}C(i+t,i)\\ =&\sum_{i=0}^{n-1}(S(i+t)^3P(i)+S(i+t)P(i)^3-2S(i+t)^2P(i)^2)\\ =&\sum_{i=0}^{n-1}S(i+t)^3P(i)+\sum_{i=0}^{n-1}S(i+t)P(i)^3-2\sum_{i=0}^{n-1}S(i+t)^2P(i)^2 \end{aligned}\]

可以注意到三项都是等差卷积，因此我们可以都用$FFT$进行加速，时间复杂度为$O(m\log_2m)$。

LUOGU的一道题目

例子2：给定长度为$n$的模式串$P$和一个字符串$S$，要求找到$P$在$S$中所有出现位置的起始下标。这里匹配的含义略微不同，$P$实际上给定了另外两个序列$A$和$B$，$S(i)$与$P(j)$可以匹配当且仅当$S(i)$能与$A(j)$或$B(j)$中的至少一个匹配。

继续感受惩罚函数的美好吧。我们重新定义惩罚函数$C(i,j)=(S(i)-A(j))^2(S(i)-B(j))^2$。之后展开匹配函数：

\[\begin{aligned} M(t)=&\sum_{i=0}^{n-1}C(i+t,i)\\ =&\sum_{i=0}^{n-1}(S(i+t)-A(i))^2(S(i+t)-B(i))^2\\ =&\sum_{i=0}^{n-1}(S(i+t)^2-S(i+t)(A(i)+B(i))+A(i)B(i))^2\\ =&\sum_{i=0}^{n-1}S(i+t)^4+\sum_{i=0}^{n-1}A(i)^2B(i)^2\\ &-2\sum_{i=0}^{n-1}S(i+t)(A(i)+B(i))A(i)B(i)\\ &+\sum_{i=0}^{n-1}S(i+t)^2((A(i)+B(i))^2+2A(i)B(i))\\ &-2\sum_{i=0}^{n-1}S(i+t)^3(A(i)+B(i)) \end{aligned}\]

上面的函数头两项是简单的前缀和，后面3项是等差卷积，因此时间复杂度为$O(m\log_2m)$。

一道CF题目。

字典序最小子序列

对于子序列$t$，若$t_i>t_{i+1}$，则称$i$是$t$的一个border（即一个非严格递增段的尾部）。这里特殊认为$|t|$也是一个border。记$s(k)$表示字典序最小的长度为$k$的子序列。

命题1：对于长度为$m$的序列$t$，其字典序最小的长度为$m-1$的子序列一定可以通过删除$t$中最左边的border来得到。

这是很显然的，删除一个非border，只会让自己的字典序增大，而删除一个border才可能减小字典序。删除最左边的border的效果是最好的（因为字符串比较是从左到右比较）。

命题2：$s(k-1)$是$s(k)$的子序列。

如果$s(k-1)$是$s(k)$的前缀，则命题显然成立。否则一定存在一个下标$i$，满足$\forall j\lt i(s(k-1)_j=s(k)_j)$且$s(k-1)_i\lt s(k)_i$。考虑到$s(k)$是字典序最小的长度为$k$的子序列，因此$s(k-1)[i..k-1]$是$a$的后缀。记$l$表示$s(k)_1,\ldots,s(k)_{i-1}$是$a[1..l]$的子串，但不是$a[1..l-1]$的子串，则此时$s(k)_i$应该是$a[l..n-k+i]$中的最小值。之后拼接$s(k-1)[i..k-1]$。

命题3：$s(k-1)$可以通过$s(k)$删除最左边border得到。

由于$s(k-1)$是$s(k)$的最小子序列，而删除左边border可以让子序列最小。

给定长度为$n$的序列$a_1,\ldots,a_n$。很显然其长度为$k$的字典序最小的子序列$s(k)$是唯一的，记$f(k)=\sum_{i=1}s(k)_i$。要求输出$f(1),\ldots,f(n)$。

首先$f(n)=a$，之后我们不断从$f(i+1)$中删除最左边border得到$f(i)$。注意到最左边border的后一个字符的位置始终是递增的，因此可以枚举最左边border的后一个字符的位置即可。整体的时间复杂度为$O(n)$。

判断A是否是B的子串

要判断$A$是否是$B$的子串，我们可以使用贪心算法，记$f(i)$表示A的长度为$i$的前缀，是$B$的长度为$f(i)$的前缀的子串，且$f(i)$尽可能小。

可以发现$f$是个递增函数，此时$f(i)$等于最小的$j$，满足$j>f(i-1)$且$B_j=A_i$。因此我们我们用线性算法解决这个问题，时间复杂度为$O(|A|+|B|)$。

这里特殊提一下，如果有很多判断子串的请求，要求计算$A_1,A_2,\ldots,A_k$是否是$B$的子串。这时候我们可以预处理$B$，令$next(i,j)$表示最小的下标$t$，满足$t>i$且$B_t=j$。之后每次判断我们可以根据$next$表快速跳转，时间复杂度为$O(C|B|+\sum_{i=1}^k|A_i|)$，其中$C$是字符集大小。

本质不同的子串数目

给定一个长度为$n$的字符串$S$，字符集为$C$。要求计算字符串有多少本质不同的子串（子串是通过从原串删除若干个字符后得到的新的字符串，原字符串和长度为0的空串也认为是子串）。两个子串$A,B$本质不同，当且仅当长度不同或存在某个下标$i$，满足$A_i\neq B_i$。

如果不考虑本质不同，那么总共有$2^n$种子串。下面来考虑有多少本质不同的字符串。

我们回忆另外一个问题，给你两个字符串$A,B$，判断$A$是否是$B$的子串。这个问题我们有$O(|A|+|B|)$时间复杂度的贪心算法。即对于每个$A$的长度为$i$的前缀$A(i)$，记录最短的$B$的前缀$B(j)$，满足$A(i)$是$B(j)$的子串，这里我们记$P(i)=j$。可以发现$P(i)$是递增函数，因此我们找到$P(i-1)$后，一定有$P(i)>P(i-1)$，我们逐一扫描$B$的第$P(i-1)$个字符后面的字符即可。

可以发现上面提到的算法，对于给定的$A$其流程是固定的，但是对于不同的$A$，其流程两两不同。因此我们可以记$f(i)$表示满足最后一个字符恰好匹配$S_i$的本质不同的序列数目（很显然在这时候没有统计到的序列最后都不会和这些序列冲突），记$N(i,c)$表示$S$中第$i$个位置后字符$c$出现的首个下标，那么$f(i)$可以对$f(N(i,c))$产生贡献，其中$c\in C$。因此时间复杂度为$O(n|C|)$，空间复杂度为$O(n|C|)$。

提供一道题目：SRM750 PurpleSubsequences。

最短的非子串

给定长度为$n$的序列$A$，要求找出所有不是$A$的子串中长度最短的序列，如果有多个，找出其中字典序最小的。其中字符集$C$为所有小写英文字母。

我们知道如何判断一个字符串是否是$A$的子串，我们记$N(i,x)$，表示最小的$j$，满足$j>i$且$A_j=x$，如果不存在，就记$j$为$n+1$。记$B$为我们的答案。可以发现B[2..]不是A[N(0,B_1)+1..]的子串且是最短的，因此如果我们希望$B$尽可能短，则对应的希望$N(0,B_1)$尽可能大。

我们可以建立一副图，并从顶点$i$到顶点$N(i,c)$建立一条长度为1的有向边，有向边上写着字符$c$。那么问题就变成了计算从顶点$0$到顶点$n+1$的最短路径。在保证路径最短的前提下，我们要找出路径上字符组成的字符串字典序最小的那一条。

由于是无环图，因此可以直接DP解决掉。时间复杂度为$O(Cn)$。

提供一道题目。

一些子串查询问题

题目1：给定$n$个名称，每个名称都有一个权重。之后有$q$个询问，询问分为两类，一类是改变某个名称的权重，还有一类就是提供另外一个字符串$s$，查询所有名称是这个字符串子串的名称的最大权重。这里$1\leq n,m\leq 5\times 10^5$，且输入的字符串总长度为$M$，满足$1\leq M\leq 10^6$，且每个名称不同。

提供一道问题https://codeforces.com/contest/1437/problem/G。

这个问题涉及到子串查询，我们可以在名称上构建AC自动机。之后在fail树上建立LCT。之后每次查询，如果是修改，我们就行该对应名称中止符所在顶点的权重。而对于查询，我们查询遍历的所有顶点到根路径上权重最大的顶点的权重。这个过程总的时间复杂度为$O((n+M)\log_2n)$。

题目2：给定$n$个名称，每个名称都有一个权重。之后有$q$个询问，询问分为两类，一类是改变某个名称的权重，还有一类就是提供另外一个字符串$s$，查询所有名称包含这个字符串作为子串的名称的最大权重。这里$1\leq n,m\leq 10^5$，且输入的字符串总长度为$M$，满足$1\leq M\leq 10^5$，且每个名称不同。

我们这里是希望查询以输入的字符串作为子串，而不是一名称作为子串。我们知道AC自动机的子串查询是对于被查询的串而不是构建的串。因此我们离线请求，根据请求中的$s$构建AC自动机。之后对于名称$x$，我们发现其最多匹配$O(|x|\sqrt{M})$个字符串，每个顶点的fail链上最多有$\sqrt{M}$个不同的字符串（没给字符串长度不同）。因此总共的匹配关系仅有$O(M\sqrt{M})$，我们可以线性处理所有的查询，总的时间复杂度为$O(M\sqrt{M})$。

一些自动机

KMP自动机

KMP自动机实际上就是维护了模式串$P$的每个前缀串的border信息。当我们在KMP自动机上跑字符串$S$，其匹配的实际上是$P$的所有前缀集合与$S$的所有后缀集合中的交集中的最长元素。

KMP自动机可以一边构建一边匹配，并且KMP自动机不需要关心字符集的大小。

AC自动机

AC自动机实际上只是把KMP自动机扩展到了前缀树上。每个结点$x$的fail指针$y$，满足$y$是$x$的border。当我们在AC自动机上跑字符串$S$，其匹配的实际上是是$P$（注意这里的$P$可能有多个）的所有前缀集合与$S$的所有后缀集合中的交集中的最长元素。

AC自动机还有很多优异的特性。

AC自动机支持多模匹配，这是其它自动机都不能支持的
AC自动机的fail指针是树形的，这意味着可以在这上面使用一些树上算法
AC自动机的构建和匹配都是可以实现真$O(1)$的，而不是摊还$O(1)$。

但是AC自动机也有一些缺点，AC自动机不能边构建边匹配，即构建必须发生在匹配之前。

题目1：限定字符集为小写字母。给定总长为$m$的若干模式串。给定长度为$n$的字符串$S$，要求在$S$尾部添加最少的字符，使得$S$以某个模式串作为后缀。其中$1\leq n,m \leq 3\times 10^5$。

先为模式串构建AC自动机，之后在上面跑$S$。考虑我们每增加一个字符，只会使得匹配结点改变一次。我们可以在匹配结点之间建立边，每条边代表需要一个字符才能进行转移。之后实际上我们要找从当前结点出发，到某个终止符的最短距离，跑个Dijkstra即可，时间复杂度为$O(26n\log_2n)$。

题目2：限定字符集为小写字母。给定总长为$m$的若干坏字符串，要求统计有多少长度恰好为$n$的字符串，不包含任何坏字符串作为其连续子串。问存在多少这样的满足条件的字符串，结果对$p$取模。这里$1\leq m\leq 10^3$，$1\leq n\leq 10^4$。

利用坏字符串构建AC自动机。之后我们构建目标串。我们把AC自动机中的每个结点理解成状态，在目标串尾部增加新元素，会导致匹配最终状态的改变。我们记$dp(i,j)$表示构建长度为$i$，且匹配最终状态为$j$的方案数。时间复杂度为$O(26nm)$。

题目3：限定字符集为小写字母。给定$n$个总长为$m$的字符串，为每个字符串计算有多少给出的字符串是它的子串。其中$1\leq n\leq 10^4$，$1\leq m\leq 10^6$。

为所有字符串构建AC自动机。之后我们发现实际上我们关心树上$O(n)$个结点之间的可达性。我们可以通过tarjan算法求解可达性，时间复杂度为$O(26m)$。

还有一种更加简单的方式，我们对每个结点处理出沿着fail链上升时遇到的第一个终止符。之后我们为每个终止符创建一个大小为$n$的bitset。之后我们用每个模式串$i$作为输入进行匹配，对匹配遇到的顶点，在其最近终止符上打上$i$的标记。这样就能处理出有哪些字符串是其它字符串的子串。时间复杂度为$O(26m+n^2)$。

提供一道题目。

题目4：限定字符集为小写字母。给定总长为$m$的若干模式串，以及长度为$n$的字符串$S$。要求统计每个模式串在$S$中的出现次数。其中$1\leq n, m\leq 10^6$。

首先为所有模式串构建AC自动机。之后在自动机上跑$S$，每次匹配新的字符，就将最后匹配结点的出现计数增加1。之后考虑fail树，每个结点的最终出现次数，都是以自己为根的子树中所有结点的计数之和。时间复杂度为$26(n+m)$。

后缀自动机

后缀自动机，原理实际上我也不是很懂，只是会实现而已。

后缀自动机中每个结点也有个fail指针，不过这个fail指针指向的是当前结点right集合的最小真超集。因此fail指针也是树形的。

后缀自动机可以一边构建一边匹配。

在后缀自动机上跑字符串$S$，得到的是$S$的后缀集合和模式串的$P$的所有连续子串集合的交集中的最大元素。因此可以很容易通过后缀自动机实现最长公共连续子串算法。

后缀自动机中每个结点都对应一个连续子串集合，且这些结点的连续子串集合是彼此不相交的。因此可以利用后缀自动机实时统计模式串中的本质不同连续子串的数目。

后缀自动机的转移是拓扑序的，换言之，如果可以从$A$转移到$B$，则不可能从$B$转移到$A$。

题目1：给定一个字符串$s$，初始是空串，之后有$n$个追加操作，每个操作向$s$尾部增加一个小写字母。要求计算每个操作完成后$s$有多少个不同的子串。其中$1\leq n\leq 10^6$。

后缀自动机可以实时统计不同子串数目，每个结点对应若干个长度不同的子串。因此只需要监控结点的状态即可。时间复杂度为$O(26n)$。

题目2：给定一个长度为$n$的字符串$s$，找到出现至少两次的最长子串并输出（空串也是合法的）。其中$1\leq n\leq 10^6$。

提供一道题目。

首先我们在$s$上构建后缀自动机后，在原串上跑后缀自动机，同时计算每个结点的匹配次数。

之后我们只需要找到匹配次数超过$1$的长度最大的结点即可。可以在匹配后缀自动机的时候同时计算每个结点第一次匹配对应的下标，这样就能根据结点确定具体的串位置。

时间复杂度为$O(26n)$。

题目3：给定长度为$n$的字符串$s$，将$s$的所有不同非空子串排序后，找到其中第$k$大的结果并输出。其中$1\leq n\leq 10^6$，$k$是一个合法值。

提供一道题目。

首先需要注意到后缀自动机的状态和状态转移是一个拓扑图，因此我们可以在上面进行记忆化搜索，定义$h(x)$表示从结点$x$开始转移的字符串数目。

之后我们从自动机的根开始递归，每次进入顶点的时候先减去$1$。

时间复杂度为$O(26n)$。

题目4：给定长度为$n$的字符串$s$，将$s$的所有非空子串排序后，找到其中第$k$大的结果并输出。其中$1\leq n\leq 10^6$，$k$是一个合法值。

提供一道题目。

类似于题目3，但是这里在进入顶点的时候减去的是这个顶点对应的子串在原串中出现的次数。

时间复杂度为$O(26n)$。

题目5：给定$m$个总长为$n$的字符串$s_1,s_2,\ldots,s_m$，找到它们的最长公共子串。其中$1\leq m\leq n\leq 10^6$。

提供一道题目。

首先我们找到这些串中最短的串，根据其构建后缀自动机。很显然公共子串一定是这个后缀自动机的某个结点代表的串。

之后我们将$m$个字符串分别丢到后缀自动机上跑，同时记录每个结点的最大匹配长度。很显然这样最后会导致每个结点记录$m$个长度，我们只需要保留其中最小值即可，因此这样只需要记录两个长度信息，一个是之前所有匹配的最大匹配长度的最小值，一个是当前匹配的最大匹配长度。

由于后缀自动机是根据长度不超过$\frac{n}{m}$的串构建的，因此总的时间复杂度为$O(26n)$。

区间本质不同子串数

考虑这样一个问题，给定一个长度为$n$的字符串$s$，之后要求回答$q$个请求，每个请求给定$l,r$，指定$s$的子串$s[l..r]$，现在要求回答，这个子串中存在多少本质不同的非空子串。

这里$1\leq n\leq 10^5$，$1\leq q\leq 10^6$。

提供一道题目。

很早以前在codeforces的某篇博客中看到这个问题，但是当时觉得解法太复杂，所以没去看，结果后来遇到了类似的问题。

考虑给定一个数组$x_1,\ldots,x_n$，以及$q$个请求，每个请求查询一个区间，问区间中有多少个不同的值。这是一个经典问题，一般做法就是离线请求处理，如果我们扫描到$x_i$，则将$x_i$上一次出现的位置减$1$，而$i$处增加$1$，之后请求就是统计区间和。我们可以考虑使用相同的技术来维护本质不同的非空子串。

首先我们考虑在字符串$s$上建立后缀自动机，之后用LCT维护fail树。

我们维护一个数值$a_i$，其中$a_i$表示存在多少个本质不同的子串，以$i$作为开头。

对于给定的$r$，我们考虑每个所有子串$s[1..1],s[1..2],\ldots, s[1..r]$，以及它们的贡献。假设现在仅$s[1..r]$未处理，其余的贡献都已经计算完了。那么$s[1..r]$实际上引入了$r$个不同的子串。对应的我们需要将$a_1,\ldots,a_r$全部增加$1$。这就要求我们能快速找到这$r$个子串之前出现的开始下标。$s[1..r]$实际上对应后缀自动机的某个状态，以及对应fail树上的某个结点$u$。我们需要遍历所有$u$的祖先结点，并且撤销这些祖先结点之前所做的贡献，并标记它们最近一次出现的右端下标为$i$。显然暴力是不可接受的。由于我们用LCT维护了fail树，因此查找到根的路径可以理解为一次access操作。实际上仔细观察可以发现LCT中的所有连续的重链（splay树），都拥有相同的右端下标，且它们对应的子串长度是一个连续的范围。那么我们在access合并splay树的时候，可以将它们做的贡献撤销（对应对于$a$的一次区间更新）。由于access的摊还时间复杂度为$O(\log_2n)$，因此可以认为摊还撤销次数为$O(\log_2n)$级别的。

我们可以用线段树来维护$a$，因此总的时间复杂度为$O((n\log_2n+q)\log_2n)$。

如果我们将线段树替换为持久化线段树，则可以通过相同的时间复杂度支持在线请求。

回文自动机

回文自动机中每个顶点表示一个独一无二的回文子串。我们可以为每个结点增加额外的访问时间和访问次数来从原串中恢复这样的回文子串。

回文自动机可以支持双端插入。具体原理就是回文自动机中每个顶点对应的都是一个唯一的回文串。因此在发生前端插入操作的时候，可能会出现新的回文串。为此我们需要维护最长前缀回文串（和后端插入类似，后端插入也需要维护最长后缀回文串）。考虑到前端插入后新的最长前缀回文串删除两端后得到的一定是一个前端回文串，故前缀回文串可以同样的方法找到。特殊的是如果最长前缀回文串更新为全串时，需要将最长后缀回文串也更新为全串，这样两者的值才会和定义相符。

题目1：给定字符串$s$，统计$s$中的所有回文子串的长度和。

回文自动机裸题。

题目2：给定$n$个字符串$s_1,s_2,\ldots,s_n$，要求找到这些字符串的最大公共回文子串。

提供一道题目

我们可以先考虑$n=2$的情况。这时候我们要找两个字符串的最大公共回文子串。

设$x,y$是两个不同的不会出现在字符串中的字符。我们在字符串$s_1$上建立回文自动机，之后统计$s_1$上每个回文出现次数，记作版本$1$。之后我们继续追加$xys_1$。同时统计每个回文出现次数，记作版本$2$。如果某个回文出现次数的版本1大于0，且版本2大于版本1，那么就是$s_1$和$s_2$的一段公共回文串。遍历所有顶点即可。

现在考虑$n$任意大的情况，我们可以如法炮制。但是可以加上一些优化，先将字符串按照长度从小到大排序处理。之后在建立完$s_1xys_2$并处理完后，我们可以把后续加入$xys_2$对应的顶点全部删除掉。这样时间复杂度就能优化到$O(C\sum_{i=1}^n|s_i|)$。其中$C$是字符集大小。

题目3：实现双端插入回文自动机

提供一道题目题目。

字符串排序

给定$n$个总长为$m$的字符串，要求将它们排序，并输出排序后的结果。

我们不能直接对字符串调用排序过程，因为比较排序可能会导致某个字符串被比较最多$n-1$次，如果这个字符串比较长，那么会导致时间复杂度达到$O(nm)$。但是比较特殊的是如果你使用归并排序或快速排序，时间复杂度将约束到$O(m\log_2n)$，因为每一层的计算时间复杂度都是$O(m)$。

一种比较简单的方式是为所有字符串建立前缀树，之后在前缀树上先序遍历就可以得到所有字符串的排序结果。时间复杂度和空间复杂度都为$O(\Sigma m)$。其中$\Sigma$是字符集大小。

上面的过程依赖于字符集的大小，如果仅考虑小写字母，那么时间复杂度也会达到将近$O(m\log_2m)$级别，并且更大问题是空间复杂度大容易出问题。

一种更高效的方案是将所有字符串拼接在一起，两个字符串之间插入一个足够小的字符作为间隔。之后线性求后缀数组（DC3或SAIS）就可以得到排序的结果。这样时间复杂度为$O(n+m)$，相当高效了。

子串的比较

有时候我们会遇到问题，给一个长度为$n$的串，之后给两个区间，问这两个区间中的字符串是否相等。

上面这个问题可以使用多项式哈希解决，时间复杂度为$O(n)$预处理，$O(1)$查询。

现在考虑修改问题，判断两个区间中的字符串的大小关系，比较逻辑是字典序。

由于子串一定是某个后缀的前缀，我们可以用后缀数组来做。先算出后缀数组和lcp（最长公共前缀），之后在lcp数组上建RMQ。每次两个不同的后缀的最长公共前缀一定是lcp数组中某个区间中的最小值。之后我们可以通过找lcp快速确定不同的下标，从而进行判断。预处理时间$O(n)$，查询时间$O(1)$。

汉明距离小于$k$的子串查找

题目1：给定长为$n$的源串$s$，以及长度为$m$的模式串$p$，要求查找源串中有多少子串与模式串匹配。$s'$与$s$匹配，当且仅当$s'$与$s$长度相同，且最多有$k$个位置字符不同。其中$1\leq n,m\leq 10^6$，$0\leq k\leq 5$。

这道题无法使用KMP解决，但是可以通过哈希+二分来解决。

枚举所有可能匹配的子串，假设现在枚举的子串为$s'$，通过哈希+二分可以快速找到$s'$与$p$第一个不同的位置。之后将$s'$与$p$在这个失配位置及之前的部分删除掉，继续查找下一个失配位置。这样的过程最多发生$k$次。

总的时间复杂度为$O(m+kn\log_2m)$。

后缀平衡树

后缀平衡树是一种用于维护后缀数组的数据结构，其支持$O(\log n)$的前部插入一个字符和前部删除一个字符，并且每个请求的空间复杂度为$O(1)$，同时保持动态维护新的后缀数组。

具体实现就是利用一颗替罪羊树，每个顶点对应一个后缀，并为每个顶点维护一个浮点数权值，两个后缀的比较结果等于其权值的比较结果（因此权值两两不同）。考虑我们已经将部分后缀丢到树上了，我们该如何分配权值呢，我们可以将整颗树的权值区间设为$[0,1]$。之后递归分配，如果子树的权值区间为$[l,r]$，则子树的根的权值为$(l+r)/2$，左子树的权值区间为$[l,(l+r)/2]$，右子树的权值区间为$[(l+r)/2,r]$。当替罪羊树的某个子树发生重构的时候，我们需要重新分配权值。

可以发现由于替罪羊重构树的时候是暴力重构而非使用惰性标记，因此我们可以通过直接访问顶点的方式获得它实时权值。这一点在接下来的内容中非常重要。

考虑插入操作，我们在字符串前部插入一个新的字符。很显然新增的后缀仅一个，以新插入的字符起始。由于原树就保证了后缀数组的性质，因此我们可以递归的时候二分插入，故插入过程最多与$O(\log n)$个顶点发生比较。

我们考虑如何实现高效的比较，最简单就是用哈希，这样时间复杂度为$O(\log_2n)$每次比较。但是实际上我们考虑后缀的比较规则，如果两个后缀第一个字符不同，则结果显然，否则则一同删除第一个字符，比较新的后缀。可以发现不管是新加入的后缀还是已经存在的后缀，其删除前部字符后得到的后缀都是在后缀树中出现的后缀，换言之，我们可以通过比较权值来高效的比较它们的大小关系。因此无论是哪种情况，比较都可以$O(1)$完成。故插入的时间复杂度为$O(\log n)$。

考虑删除操作。删除操作就是直接在树上找到顶点，之后将出现次数减少一。注意和一般的替罪羊树不同，一般替罪羊树在发生重构的时候，会删除出现次数为0的顶点。但是这里我们是不能删除顶点的。原因很简单，我们需要为每个后缀记录其删除一个字符后得到的新的后缀，我们记前者为$a$，后者为$b$，如果$a$与$b$都被删除了，但是仅$b$所在的子树被重构了，这时候$b$被销毁了（或者不被销毁，但是其权值已经不正确了），之后再发生插入操作的时候，$a$就不能被正常比较了。

我们对树进行一次dfs，就可以$O(n)$得到sa数组。但是由于我们之前没有介绍销毁顶点的方法，因此随着程序运行，每次dfs的耗时也会越多。下面我们介绍一下如何正确的删除顶点。

考虑到之前提到不允许删除的原因是销毁时间可能会错乱，我们可以在树中被出现次数为$0$的顶点数超过半数的时候，对整颗树暴力重构一次，这样既能保证所有顶点按正确顺序被销毁，并且暴力重构整颗树的时间复杂度被删除顶点数所约束，且每次dfs的时间复杂度最多被翻倍，得到一个不错的均衡。

当然你也可以通过一般平衡二叉树的删点方法，就是找前驱后后继来替代自己，只是会比较复杂而已。

这里顺带一提怎么动态维护lcp数组，并支持区间查询操作。这个方法是从[Tutorial] Dynamic Suffix Arrays这篇文章学到的。

首先我们为每个结点维护一个lcp值，表示它与前驱结点对应的两个后缀的最长公共前缀的长度。

先说一下怎么查询区间lcp最小值，这个实际上就是为每个结点维护子树中lcp的最小值，之后的逻辑类似线段树，我们贪心减枝即可。可以证明时间复杂度是$O(\log n)$级别的。

在插入新的前缀的时候，会创建一个新的结点$u$，记它的后继为$v$。可以发现现在$u$和$v$的lcp值是非法的，其余结点都是合法的。考虑怎么更新这两个lcp的值。这里仅说一下怎么更新v的lcp值，如果v和u的第一个字符不同，很显然lcp值是0，否则lcp值是u与v的删除第一个字符的新的两个后缀的最长公共前缀长度，再加上1。这里我们需要借助上面提到的查询区间lcp最小值来快速计算两个后缀的lcp值。同理更新$u$，只需要找到它的前驱并相同的方式计算即可。

现在考虑在删除前缀的时候，如何维护新的lcp值。很显然删除前缀$u$后，唯一变更的是$u$的后缀$v$，而$v$的新的lcp值实际上就是u的lcp值和v的lcp值的最小值。

可以发现现在所有插入前缀、删除前缀、查询区间lcp值都可以$O(\log n)$完成。

题目1：给定一个空串$s$，要求处理$q$个请求，每个请求分三类：

向$s$尾部加入一个新字符$c$
删除$s$尾部的一个字符
给定非空串$t$，查询$s$有多少子串等于$t$

保证$1\leq q\leq 10^6$，且出现的字符串总长不超过$10^6$。

提供一道题目。

由于后缀平衡树支持的是头部插入和删除，因此我们可以用后缀平衡树维护$s$的逆序串。同理第三类请求中的$t$也需要翻转。

接下来第一类和第二类操作都是后缀平衡树的基础操作。考虑第三类操作，考虑到每个子串都是一个唯一后缀的前缀，我们可以在$t$尾部（翻转后的）加入一个无穷大的字符，得到$t'$，这样我们可以在平衡树上统计有多少后缀前$|t|$个字符不大于$t$。之后我们将$t'$尾部的最后倒数第二个字符（无穷大字符前面的那个字符）减小$1$，再次查询，可以得到有多少后缀前$|t|$个字符严格小于$t$。两者取差值就可以得到正确的结果了。

上面比较我们可以直接暴力比较，因为每次比较的时间复杂度最多为$O(|t|)$，而树高最多为$O(\log n)$，而比较最多发生树高次，因此每次查询时间复杂度为$O(|t|\log n)$。

题目2：给定一个字符串$s$，要求处理$q$个请求。请求分三类：

向$s$尾部加入一个新字符$c$
删除$s$尾部的一个字符
查询$s$中有多少不同的子串，至少出现两次。

提供一道题目。

可以发现出现至少两次的长度为$k$的子串，其出现位置对应的两个后缀的lcp至少为$k$。而实际上这样的串一定是在sa中相邻的两个后缀的公共前缀。我们只要枚举所有的在sa中相邻的后缀的公共前缀就可以一个不漏的统计所有的满足条件的子串。

下面我们考虑怎么避免重复统计。

考虑现在有三个相邻的后缀$a,b,c$，且$a,b$的lcp值为$n$，$b,c$的lcp值为$m$，那么在$b,c$的长度不超过$n$的公共前缀一定在之前已经被统计过了，而所有超过$n$，但是不超过$m$的一定未被统计。因此我们记lcp数组为$l_0,\ldots,l_x$，答案为$\sum_{i=1}^{x}\max(0,l_i-l_{i-1})$。

由于字符串支持尾部插入和删除，因此我们需要用到后缀平衡树来动态维护lcp数组。总的时间复杂度为$O(q\log_2 (

+q))$。

串联重复（Tandem repeats）

对于任意字符串$X$，称$XX$为串联重复。

一般问题都是要求找到字符串中的一些串联重复子串。

串联重复的核心技术是判断长度为$n$的字符串$S$是否存在长度为$2d$的串联重复，存在预处理$O(n)$，之后对于每个$d$都可以$O(n/d)$计算的算法。

这个算法学习自CF的某个评论。

具体做法就是维护两个数组$L$和$R$。其中$L_d(i)$表示$S_{..i}$和$S_{..i+d}$的最长公共后缀的长度（上限为$d$），而$R_d(i)$表示$S_{i..}$和$S_{i+d..}$的最长公共前缀的长度（上限为$d$）。那么存在长度为$2d$且包含$S_i$和$S_{i+d}$的串联重复，当且仅当$L_d(i)+R_d(i)>d$。

在仅考虑$d$的时候，我们只需要考虑$d\mid i$的情况，因为任意长度为$2d$的串联重复，都至少覆盖考虑的两个下标。如果这里我们使用二分+哈希，则可以将时间复杂度优化到$O(n/d\cdot \log_2n)$，但是如果使用后缀数组的方式，可以$O(n/d)$完成。

题目1：给定字符串$S$，找到其中最小的一段串联重复和最大的一段串联重复。

我们可以遍历所有的$d$，之后找到最大的和最小的即可。总的时间复杂度为$O(n\log_2n)$。

题目3：给定字符串$S$，之后重复从$S$找到最短的串联重复（如果有多个则选择最早出现的），并从$S$中删除该串联重复的后半段。之后重复这个过程，直到找不到串联重复为止。求最终得到的字符串$S$。其中$1\leq |S|\leq 10^5$。

提供一道题目。

记$f(S)$表示$S$中最短的串联重复的长度。

首先我们先证明如果我们从$S$中选择其中最短的一段串联重复，并删除一半，得到新的字符串$S'$，有$f(S)\leq f(S')$。

假设被删除的部分为$X$，则得到的新的最短的串联重复一定完整包含$X$，记这部分为$AXB$。由于$|A|+|B|\leq |X|-2$，因此一定满足$X=TBAT$，这时候可以发现原来的字符串中存在$AXXB=ATBATTBATB$，这时候可以发现一段比$XX$更短的串联重复$TT$，这显然不可能，因此证明成立。

这样我们只需要检查有哪些$d$存在串联重复，这个过程可以$O(n\log_2n)$完成。如果存在长度为$2d$的串联重复，则我们调用一个cut(d)方法，按序删除其中所有长度为$2d$的串联重复。

讲一下cut方法的具体流程。我们先证明在流程中，第一个长度为$2d$的串联重复出现的起始下标为$g(S)$，则我们删除第一个出现的串联重复后得到新的字符串$S'$，一定有$g(S)\leq g(S')$。

证明类似，如果不成立，则存在$AXB$为新的串联重复，且 $|A|+|B|\leq |X|$。可以发现$X=BA$，故原来的字符串存在$AXXB=ABABAB$，这时候最早的串联重复为$ABAB$，而非$XX$，与前提相悖，因此证明成立。

因此我们可以用滑动窗口的方法维护两个连续的长度为$d$的区间，如果两者匹配，则清空右边的窗口。这样我们就可以$O(n)$实现cut算法。而考虑到cut每次被调用的$d$都不同，因此cut最多被调用$\sqrt{n}$次。

总的时间复杂度为$O(n\sqrt{n}+n(\log_2n)^2)$如果用hash来判断，否则为$O(n\sqrt{n}+n\log_2n)$，如果用后缀数组。

最小字典序拼接字符串

给定$n$个字符串，要求选出正好$k$个字符串，将这$k$个字符串重新排列后拼接成一个字符串$S$。要求$S$的字典序最小。

提供一道题目。

假设$A$和$B$都是选中的字符串，那么如果$AB\leq BA$，则在$S$中$A$一定放在$B$之前。

但是我们还需要证明这样的排序是满足传递性的。实际上，如果我们把字符串看成一个$c$进制的整数，其中$c$表示字符集大小。因此比较关系可以重写为：

\[\begin{aligned} Ac^{|B|}+B &\leq Bc^{|A|}+A\\ A(c^{|B|}-1)&\leq B(c^{|A|}-1)\\ \frac{A}{c^{|A|}-1}&\leq \frac{B}{c^{|B|}-1} \end{aligned}\]

即这等价于每个字符串关联一个固定的有理数，而比较实际上是比较这个有理数，显然这样的比较是满足传递性的。

接下来我们可以用DP来计算仅使用$k$个字符串可以的得到的最小字典序结果。

这里如果我们使用正常的DP，这时候$dp(i,j)$表示仅考虑前$i$个字符串，从中取$j$个字符串得到的最小字典序结果，这时候会有一个问题，就是$dp(i,j)$需要存储不止一个结果，它们互为前缀。

如果我们从后向前DP，问题会变得非常简单。这时候$dp(i,j)$表示仅考虑后$i$个字符串，从中取$j$个字符串得到的最小字典序结果。这时候$dp(i,j)$只需要保留字典序最小的结果即可。

时间复杂度为$O(nkM)$，其中$M$表示最长的$k$个字符串的长度之和。

字符串的一些周期、border性质

字符串的一些等口胡性质

回文的一些性质

一些回文题目

回文的最小分解

Z algorithm

后缀树

最大表示法

惩罚函数与序列匹配问题

字典序最小子序列

判断A是否是B的子串

本质不同的子串数目

最短的非子串

一些子串查询问题

一些自动机

KMP自动机

AC自动机

后缀自动机

区间本质不同子串数

回文自动机

字符串排序

子串的比较

汉明距离小于$k$的子串查找

后缀平衡树

串联重复（Tandem repeats）

最小字典序拼接字符串

参考资料