title: 字符串总结
date: 2023-07-17 21:24:47
tags: 总结
cover: https://gitcode.net/crimson000000/picture/-/raw/blog_pic/3d136f52381284a18738fa16c6f1b361.jpg
这里放些字符串相关，总之也就是从头再学字符串了。
基本概念
border：一个字符串的真前缀，并且它和该字符串的一个真后缀相等。
周期：对于字符串 \(s\) 和一个整数 \(0 < p \le |s|\)，\(\forall i, s[i]=s[i+p]\)，则 \(p\) 为字符串 \(s\) 的周期。可以证明，一个字符串的周期等于该字符串的长度减去它的最长 border 的长度。
\(lcp(a, b)\)：\(a\) 串和 \(b\) 串的最长公共前缀。
\(lcs(a, b)\)：\(a\) 串和 \(b\) 串的最长公共后缀。
KMP
KMP 是用来求解一个字符串的所有前缀的最长 border 的算法。具体算法流程如下：
我们定义 \(next[i]\) 为该字符串长度为 \(i\) 的前缀的最长 border 长度。显然，\(next[1]=0\)。我们考虑如何用已知的 \(next[i]\) 计算后面的 \(next\)。
我们可以结合下面的图来理解：
图中我们发现 \(i-1\) 的 border 无法匹配上第 \(i\) 个位置，我们就再跳到 border 的 border。由图可以看到，border 的 border 还是原串的 border。我们就可以不断跳 border 直到匹配上第 \(i\) 位。
代码如下：
ne[1] = 0;
for(int i = 2, j = 0; i <= m; i ++ )
{
while(j && t[i] != t[j + 1]) j = ne[j];
if(t[i] == t[j + 1]) j ++;
ne[i] = j;
}
由于每轮循环 \(j\) 至多 \(+1\)，而每次跳 border 至少会让 \(j\) 减一，因此内层循环不会执行超过 \(m\) 次。总复杂度即为 \(O(|s|)\)。
例题后面有。
exKMP（z 函数）
exKMP 和 KMP 相似，但是它是用来求字符串的前缀和该字符串的某个后缀的最长匹配长度。可以想象成这个字符串往后平移，平移到某个位置后从这个字符串开头进行匹配。
在 exKMP 中，我们有一个数组 \(z_i\)，表示该字符串的前缀和第 \(i\) 个后缀（也就是 \([i, |s|]\) 这段区间）的最大匹配长度。我们考虑如何快速求出 \(z_i\)。
首先，显然的是 \(z_1=|s|\)，因为它自己和它自己匹配必定长度为 \(|s|\)，但是我们不能用这个条件，否则就没用了。我们考虑维护一个连续段，这个连续段和该字符串的前缀能够完全匹配。当现在要求的位置在连续段之外，我们只能暴力往后跑。而在连续段之内时，我们可以利用最开头的 \(z\) 值来加速递推。而当顶到连续段的边界时，我们依旧只能暴力求解。
代码如下：
inline void getz(char *s, int n)
{
z[1] = n;
for(int i = 2, l = 0, r = 0; i <= n; i ++ )
{
if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) z[i] ++;
if(i + z[i] - 1 > r) r = i + z[i] - 1, l = i;
}
}
由于每次 while 循环至少使得 \(r\) 加一，而 \(r \le n\)。因此内层循环的次数不会超过 \(n\) 次。总复杂度 \(O(|s|)\)。
manacher
manacher 算法是用来快速求解字符串中回文串的算法。具体算法流程如下：
我们先对字符串进行预处理，在左右两边加入哨兵，再在每两个字符之间加入一个相同的且在原串中不存在的字符，来使得偶回文串变为奇回文串。我们再设 \(f_i\) 为以 \(i\) 位置为中心的最长回文半径。类似于 exKMP，我们也可以维护一个相同的段，只不过这次我们要维护的是一个右端点最靠右的最长回文段。在这段之外就暴力，之内就利用之前的信息，然后再暴力扩展。
代码如下：
inline void manacher(char *t)
{
n = strlen(t + 1);
s[0] = '#', s[1] = '$';
for(int i = 1; i <= n; i ++ )
s[i << 1] = t[i], s[i << 1 | 1] = '$';
n = n << 1 | 1;
s[++ n] = ')';
for(int i = 1, mid = 0, r = 0; i <= n; i ++ )
{
f[i] = 1;
if(i <= r) f[i] = min(f[2 * mid - i], r - i + 1);
while(s[i - f[i]] == s[i + f[i]]) f[i] ++;
if(i + f[i] - 1 > r) r = i + f[i] - 1, mid = i;
}
}
时间复杂度分析同 exKMP。
AC 自动机
抽象的世界开始了
AC 自动机和 KMP 类似，都是求解字符串匹配的问题，但是 AC 自动机可以支持多模式串对一个文本串进行匹配，时间复杂度同样也是线性。
AC 自动机一开始可以看作一颗 trie 树。在 AC 自动机中，我们类似 KMP，我们维护一个 \(fail\) 指针，表示与后缀能够匹配的最长前缀所在的节点编号。不过这个 \(fail\) 指针可能指向别的字符串中的位置，但是这无关紧要，我们做的是多模式串匹配。
对于求 \(fail\) 指针，我们可以采取 bfs 的方法。因为类似 KMP，我们所有的信息都是从前面递推过来的，因此我们只要知道所有深度小于当前节点的信息，我们就可以递推出来。我们也可以类似 KMP，一直跳 \(fail\) 指针，直到匹配或者跑到根节点。而对于匹配文本串也是一样。
在 AC 自动机中，我们可以对 \(fail\) 指针做一个优化。因为每个节点有 \(26\) 个儿子，而这些儿子大部分都没有被创建出来，我们考虑利用一下这些空数组，我们定义 \(tr[p][u]\) 为节点 \(p\) 假设有 \(u\) 这个儿子，这个儿子的 \(fail\) 指针指向的位置，这个也可以递推得到。这样我们就不用每次跳 \(fail\) 了。
代码如下：
inline void insert(char *s, int ident)
{
int p = 0;
for(int i = 1; s[i]; i ++ )
{
int t = s[i] - 'a';
if(!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
if(!id[p]) id[p] = ident;
mp[ident] = id[p];
}
inline void build()
{
queue<int> q;
for(int i = 0; i < 26; i ++ )
if(tr[0][i])
q.push(tr[0][i]);
while(q.size())
{
int t = q.front();
q.pop();
for(int i = 0; i < 26; i ++ )
{
int u = tr[t][i];
if(!u) tr[t][i] = tr[fail[t]][i];
else
{
fail[u] = tr[fail[t]][i];
din[fail[u]] ++;
q.push(u);
}
}
}
}
void query(char *s)
{
for(int i = 1, j = 0; s[i]; i ++ )
{
int t = s[i] - 'a';
j = tr[j][t];
val[j] ++;
}
}
代码来源于AC 自动机（二次加强版）。我们可以注意到，在查询出现次数时，我们为了优化复杂度，利用了树上差分的思想，某个点如果出现过，那么它 \(fail\) 指针和 \(fail\) 的 \(fail\) 也会出现。因为我们从大到小枚举节点编号，也就是 trie 树从下而上的拓扑序。直接拓扑排序的时候加上即可。
PAM（回文自动机）
我直接赫过来之前的博客得了
之前博客图挂了，还是自己复习一遍吧
PAM 中有两棵树，分别对应着字符串中的奇回文串和偶回文串。而 PAM 中的 \(fail\) 指针和 AC 自动机中相似，设 \(fail_x\) 为 \(x\) 代表的回文串的最长回文后缀所对应的节点。这个 \(fail\) 指针有利于我们插入节点。
当我们要新加入一个字符时，它可能会和原字符串中的末尾形成一个回文串。由于是回文串，因此两边同时扣掉一个字符依旧是回文串。我们发现这个回文串也就是一个回文后缀。我们直接在这个回文后缀所对应的节点后挂上这个节点即可。这个过程就可以用 \(fail\) 指针来做。
建树代码：
inline int getfail(int x, int i)
{
while(i - len[x] < 1 || s[i - len[x] - 1] != s[i]) x = fail[x];
return x;
}
inline void build(int n)
{
len[1] = -1, fail[0] = 1;
idx = 1;
for(int i = 1; i <= n; i ++ )
{
pos = getfail(cur, i);
int u = s[i] - 'a';
if(!tr[pos][u])
{
fail[++ idx] = tr[getfail(fail[pos], i)][u];
tr[pos][u] = idx;
len[idx] = len[pos] + 2;
}
cur = tr[pos][u];
}
}
SA（后缀数组）
SA 是一个把所有后缀都放到一个数组，支持动态查询一个后缀的排名的结构。在其中有两个重要数组：\(sa_i\) 和 \(rk_i\)。\(sa_i\) 表示排名第 \(i\) 的后缀为哪个，\(rk_i\) 表示第 \(i\) 个后缀的排名。
有一个很简单的构建方法就是把所有后缀都搂出来然后 sort 一下。但是字符串比较是 \(O(n)\) 的，因此这样的复杂度是 \(O(n^2\log n)\)。我们可以利用倍增，用上一层的 \(rk_i\) 来为下一层做准备。下面放一张图来理解：
每次只会对两个关键字进行比较。我们可以简单粗暴用 sort，时间复杂度 \(O(n\log^2 n)\)，但是为了少一个 \(\log\)，我们可以用基数排序，这样时间复杂度即为 \(O(n\log n)\)。
构建代码：
m = 127;
for(int i = 1; i <= n; i ++ ) rk[i] = s[i];
for(int i = 1; i <= n; i ++ ) cnt[rk[i]] ++;
for(int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
for(int i = n; i >= 1; i -- ) sa[cnt[rk[i]] -- ] = i;
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
for(p = 0, i = 1; i <= n; i ++ )
{
if(oldrk[sa[i]] == oldrk[sa[i - 1]])
rk[sa[i]] = p;
else rk[sa[i]] = ++ p;
}
for(w = 1; w < n; w <<= 1)
{
m = p;
for(p = 0, i = n; i > n - w; i -- ) id[++ p] = i;
for(i = 1; i <= n; i ++ )
if(sa[i] > w)
id[++ p] = sa[i] - w;
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; i ++ ) ++ cnt[rk[id[i]]];
for(int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
for(int i = n; i >= 1; i -- ) sa[cnt[rk[id[i]]] -- ] = id[i];
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
for(p = 0, i = 1; i <= n; i ++ )
{
if(oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w])
rk[sa[i]] = p;
else rk[sa[i]] = ++ p;
}
}
我们还可以求出一个数组 \(height_i\)，表示 \(lcp(sa_i, sa_{i-1})\)。有一个引理：\(heigt[rk[i]] \ge height[rk[i-1]]-1\)，这样我们就可以直接暴力求了。
对于 \(height\) 数组，有这样一个用处：\(lcp(sa[i], sa[j])=\min \{height[i + 1]\cdots height_{j} \}\)。这样就可以把 \(lcp\) 转化为 rmq 问题来处理了。
SAM（后缀自动机）
我会，以后再写
后缀平衡树
我不会，以后再学习
一些题目
Matching
对于整数序列 \((a_1,a_2,\cdots,a_n)\) 和 \(1\sim n\) 的排列 \((p_1,p_2,\cdots,p_n)\)，称 \((a_1,a_2,\cdots,a_n)\) 符合 \((p_1,p_2,\cdots,p_n)\)，当且仅当：
-
\(\{a\}\) 中任意两个数字互不相同；
-
将 \((a_1,a_2,\cdots,a_n)\) 从小到大排序后，将会得到 \((a_{p_1},a_{p_2},\cdots,a_{p_n})\)。
现在给出 \(1\sim n\) 的排列 \(\{p\}\) 和序列 \(h_1,h_2,\cdots,h_m\)，请你求出哪些 \(\{h\}\) 的子串符合排列 \(\{p\}\)。
数据范围：\(n, m\le 1000000\)。
KMP 好题。我们考虑将判定相等转化一下，可以变为：在它之前比它小的数的个数。这个映射很容易证明是和原来的序列一一对应的。因此我们可以用这个条件来判定相等。我们先预处理出来 \(p\) 中的这个值，记为 \(cnt_i\)。然后由于要求匹配，我们可以用 \(KMP\)。查询小于它的数可以直接用树状数组来做。
时间复杂度 \(O(n\log n)\)。
Prefix-Suffix Palindrome
给定一个字符串。要求选取他的一个前缀（可以为空）和与该前缀不相交的一个后缀（可以为空）拼接成回文串，且该回文串长度最大。求该最大长度。
数据范围：\(\sum n\leq 10^6\) 。
我们考虑如何拼接才是最大的。显然，我们先选取最长逆序相等的前后缀，然后再找一个和这个前后缀相交的回文串即可。如何求这个最长逆序相等的前后缀呢，我们可以把字符串反转后拼到原串后，跑一遍 exKMP，\(z_{n+1}\) 即为所求，然后再对整个串跑马拉车，之后枚举每个位置能否拼上这个前缀或后缀即可。
最长双回文串
输入长度为 \(n\) 的串 \(S\)，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(|X|,|Y|≥1\)）且 \(X\) 和 \(Y\) 都是回文串。
数据范围：\(2\leq |S|\leq 10^5\)。
我们先对原串跑一遍马拉车，求出每个点所对应的最长回文半径，然后从后往前递推出一个数组 \(maxl_i\)，表示 \(i\) 为最左端的回文串的最长长度。然后枚举每个点，看最长能拼成多长的双回文串。
动物园
给定字符串 \(s\)，设 \(num[i]\) 为对于 \(s\) 前 \(i\) 个字符构成的字符串，长度不大于 \(\left \lfloor \frac{i}{2} \right \rfloor\) 的 border 的数量。求出所有 \(num[i]+1\) 的乘积。
数据范围：\(|s|\le 10^6\)。
我们考虑暴力：我们对于每个点暴力跳 \(next\)，这样就能统计出所有的 \(num\)。但是如果字符串所有的字符都相同就寄了。因此我们考虑用前面的数据加速一下。
因为 border 的 border 也是 border，因此我们可以得到一个结论：\(num[i]=num[j]+1\)，其中 \(j\) 为 \(1\sim i\) 第一个不超过 \(\left \lfloor \frac{i}{2} \right \rfloor\) 的 border。根据这个我们就可以加速递推了。我们维护一个大小始终不超过 \(\left \lfloor \frac{i}{2} \right \rfloor\) 的指针 \(j\)，依旧按照 kmp 的思路找 border，一旦发现超过了 \(\left \lfloor \frac{i}{2} \right \rfloor\) 就跳 \(next\)，直到满足条件然后更新即可。
时间复杂度 \(O(n)\)。
优秀的拆分
如果一个字符串可以被拆分为 \(\text{AABB}\) 的形式，其中 \(\text{A}\) 和 \(\text{B}\) 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。现在给出一个长度为 \(n\) 的字符串 \(S\)，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。
数据范围：\(n\le 30000\)。
我们考虑将 \(A\) 部和 \(B\) 部分开，我们设 \(f_i\) 为 \(i\) 位置从左有多少方案可以拼成 \(\text{AA}\)，设 \(g_i\) 为从 \(i\) 位置往右有多少方案可以拼成 \(\text{BB}\)。则最终答案即为 \(\sum f_i\times g_{i+1}\)。
我们考虑如何求出 \(f_i\)，\(g_i\) 则同理。我们先枚举 \(\text{A}\) 的长度，我们每隔 \(k\) 个位置建立一个检查点，那么这个 \(\text{AA}\) 一定会经过两个检查点，可以见下图：
我们只需要考虑两个相邻检查点往前的 \(lcs\) 和往后的 \(lcp\)，看一下是否能重合上即可。而重合部分是我们可以自由调整的，我们就把一段区间的 \(f\) 都增加 \(1\) 即可，用差分维护。
时间复杂度 \(O(n\log n)\)。
所有公共子序列问题
给定两个字符串 \(A, B\)，求出 \(A\) 和 \(B\) 所有本质不同的公共子序列的数量。
数据范围：\(|A|,|B|\le 3000\)。
本题介绍一种新自动机：子序列自动机。具体的说，给定字符串 \(s\)，我们设 \(ne[i][c]\) 为 \(i\) 点之后第一个字符 \(c\) 出现的位置。构建直接从后往前扫即可。
它的用处主要有：统计字符串不同子序列个数、查询一个字符串是否是该字符串的子序列、两个字符串的公共子序列、因此本题说是子序列自动机的板子题也可以其实。
回到这题，我们可以同时对两个字符串在两个子序列自动机上走，每次枚举下一个字符填什么，然后走就完事了。统计答案也可以像在 DAG 上统计一样，DP 或者记忆化即可。
残缺的字符串
给定两个字符串 \(A, B\)，两个字符串中都可能出现通配符 *，表示这个位置可以为任意一个字符。求出对于 \(B\) 的每个位置 \(i\)，从这个位置开始连续 \(m\) 个字符形成的子串能否和 \(A\) 成功匹配。
数据范围：\(|A|, |B| \le 3\times 10^5\)。
这里介绍一个新东西：FFT 求字符串匹配。
先考虑没有通配符的情况，我们将每个位置附一个权值，那么两个字符串 \(a, b\) 从 \(1\) 开始匹配，成功匹配的条件即为：\(\sum \limits_{i=0}^{m-1} (a_i-b_i)^2\)。
而对于有通配符的情况，我们可以把通配符的权值设置为 \(0\)，同时判定成功的条件改为：\(\sum \limits_{i=0}^{m-1} (a_i-b_i)^2a_ib_i\)。而对于每一个位置，我们写出的式子就是下面这个样子：
\[\sum \limits _{i=0}^{m-1}(a_i-b_{i+k})^2a_ib_{i+k} \]展开即为差卷积形式，NTT 即可。
时间复杂度 \(O(n\log n)\)。
歌唱王国
给定字符集大小 \(n\) 和一个长度为 \(m\) 的字符串 \(a\)。每次随机生成一个字符集中的字符放到字符串 \(b\) 后（\(b\) 初始为空），当 \(b\) 中出现 \(a\) 的时候停止。求最终的期望长度。
数据范围：\(n, |a|\le 10^7\)。
我们设 \(f_i\) 为长度为 \(i\) 时停止的概率，\(g_i\) 为长度为 \(i\) 时未停止的概率。我们再写出这俩玩意的生成函数 \(F(x)=\sum f_i x^i\) 和 \(G(x)=\sum g_i x^i\)。
根据定义，我们很容易能写出 \(F(1)=1\)，因为最终总会结束，因此和一定为 \(1\)。而我们要求的答案为 \(F'(1)\)，因为根据期望的定义，我们的答案就是 \(\sum i\times f_i\)。求导就可以得到这个系数的多项式。
接下来就是推式子时间：
显然的，\(g_i=g_{i+1}+f_{i+1}\)，因为未结束的时候再放字符要么结束要么不结束。比较系数可以得到这个式子：
\[xG(x)+1=F(x)+G(x) \]接下来这个式子不是特别显然。我们考虑在没有结束的局面下强行在后面构造出来一个 \(a\)，那么这时一定会结束。但是在这个结束前可能会提前结束，见下图：
因此我们只需要枚举 \(a\) 的 border 即可。这里我们前面还要构造出前面的那一部分 \(a\)，对齐系数后我们的式子就是：
\[G(x)\times \left ( \frac{1}{n}x \right )^m=\sum \limits _{i=1}^{m}F(x)\times \left ( \frac{1}{n}x \right )^{m-i}[1\sim i \ is\ \text{border}] \]我们得到这两个式子后再推推。把上面那个式子两边求导，得到：
\[F'(x)=xG'(x)-G'(x)+G(x)=(x-1)G'(x)+G(x) \]我们把 \(x=1\) 带入即可得到 \(F'(1)=G(1)\)。再代入上面特别长的那个式子，可以得到：
\[\begin{aligned} G(1)\times \left ( \frac{1}{n} \right )^m & = \sum \limits _{i = 1}^{m}F(1)\times \left ( \frac{1}{n} \right )^{m-i}[1\sim i \ is\ \text{border}]\\ G(1)&=\sum \limits _{i = 1}^{m}F(1)\times n^i[1\sim i \ is\ \text{border}]\\ G(1)&=\sum \limits _{i = 1}^{m}n^i[1\sim i \ is\ \text{border}] \end{aligned} \]直接 \(O(n)\) 算即可。