NOI 一轮复习 VI：字符串

本文是 NOI 一轮复习的第六篇，包括各类字符串算法。

前置知识

我们记字符集为 $\Sigma$ ，字符串是由若干字符集中的元素构成的序列。

字符串哈希

即序列哈希，快速比较两个序列的相等情况。一般来讲我们采用 $b$ 进制方式的哈希，即 $f(s)=\sum_{i=1}^{l}s_i\times b^{l-i}$ 。

inline u64 q(u64 *f, int l, int r) { return f[r] - f[l - 1] * p[r - l + 1]; }

字典树

本质上是一种自动机结构，不再赘述。

字符串周期结构

定义 $p$ 是串 $S$ 的周期，当且仅当 $p\le |S|$ 且 $S_i=S_{i+p}$ ，如果满足 $p\mid |S|$ 则称 $p$ 是 $S$ 的整周期。

称 $T$ 是串 $S$ 的 Border，当且仅当 $T$ 是 $S$ 的前缀且 $T$ 是 $S$ 的后缀，但是 $T\ne S$ 。

结论：若 $p$ 是 $S$ 的周期，当且仅当 $|S|-p$ 是 $S$ 的 Border。

周期引理：若 $p,q$ 是 $S$ 的周期，且 $p+q-\gcd(p,q)\le |S|$ ，那么 $\gcd(p,q)$ 是 $S$ 的周期。

短周期结构：根据周期引理，对于长度不超过一半的周期，都有其 $\gcd$ 是周期，那么字符串的所有长度不超过其一半的周期都是其最短周期的倍数。

Border 结构：字符串的所有周期或 Border 形成了 $O(\log n)$ 个值域不相交的等差数列。

[WC2016] 论战捆竹竿

求字符串 $S$ 的所有周期长度的线性组合可以组成多少个 $[1,w]$ 内的数。

拆成 $\log$ 个等差数列，直接使用 Dijkstra 做同余最短路。在转移一个等差数列时，如果在 $\bmod x$ （首项）意义下不优，则直接 break 掉。时间复杂度 $O(n\log^2 n)$ ，代码。

KMP 算法

KMP 算法用于求出 $nxt$ 数组：当前位置的最长 Border。求解过程使用增量法：如果当前位置失配，则跳到上一个匹配成功的位置。匹配成功的位置为其势能，因此时间复杂度为 $O(n)$ 。

for (int i = 2, p = 0; i <= m; ++i) {
    while (p && s2[i] != s2[p + 1]) p = nxt[p]; 
    if (s2[i] == s2[p + 1]) ++p; 
    nxt[i] = p; 
}

KMP 自动机的状态集合 $Q$ 为 $0\sim |S|$ ，如果当前识别的字符串为 $t$ ，那么每个节点 $i$ 表示已经输入的所有字符 $t[1\dots p]$ 与 $s$ 的最大匹配长度为 $i$ ，即满足 $s[p-i+1,p]=s[1,i]$ ，转移函数为：

$\delta(i, c) = \begin{cases} i+1 ,& s_{i + 1} = c, \\ 0 ,& s_{i + 1} \neq c \land i = 0, \\ \delta(nxt_i, c) ,& s_{i + 1} \neq c \land i \neq 0. \\ \end{cases}$

int tr[1005][26];
for (int i = 0; i <= n; ++i)
    for (int j = 0; j < 26; ++j) {
        if (i < n && s[i + 1] == j + 'a') tr[i][j] = i + 1;
        else if (i) tr[i][j] = tr[nxt[i]][j];
    }

CF1163D。找一个模式串在字符串中的出现次数，而看到可以在 * 上填任意一个字母又是经典 DP 问题。对 $s,t$ 建出 KMP 自动机，设 $f(i,j,k)$ 考虑到 $c$ 的第 $i$ 位，此时在 $s$ 的 KMP 自动机的节点 $j$ ， $t$ 的 KMP 自动机的节点 $k$ 的最大答案。采用刷表法转移，模式串 $S$ 在转移到节点 $|S|$ 时有贡献。初始 $f(0,0,0)=0$ ，转移 $f(i+1,trs_{j,c_{i+1}},trt_{k,c_{i+1}})=\max\{f(i,j,k)+w\}$ ，目标 $\max\{f(n,j,k)\}$ 。代码。

Aho-Corasick 自动机

例题

字符串回文结构

Manacher

回文自动机

例题

字符串子串结构

通常来说，刻画 $S$ 的子串结构的方式有：后缀数组、后缀自动机、后缀树。

神风敢死队炸毁了此处的内容。

本部分将在 NOI2024 前进行完善。

后缀数组

SA 例题

后缀自动机

SAM 是一个接受字符串 $S$ 的所有后缀的最小 DFA。其满足从 $T$ 到任意状态的路径与 $s$ 的所有子串一一对应， $T$ 到终止状态集合 $F$ 的路径与 $s$ 的后缀一一对应。SAM 的有向无环转移图称为 DAWG。

下图的左侧是 abcbc 的一个 SAM：

我们先给出一些定义：

$\operatorname{endpos}(t)$ 代表 $s$ 中所有 $t$ 出现的结束位置的集合。

引理 $1$ ：字符串 $s$ 的两个非空子串 $u$ 和 $w(|u|\le |w|)$ 的 $\operatorname{endpos}$ 相同，当且仅当 $u$ 在 $s$ 中的每次出现都是以 $w$ 的后缀形式出现的。

比较显然。

引理 $2$ ：如果 $u$ 是 $w$ 的后缀，那么 $\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)$ ，否则 $\operatorname{endpos}(w)\cap\operatorname{endpos}(u)=\varnothing$ 。

也比较显然。

如果 $\operatorname{endpos}$ 集合相等，那么这两个子串可以被成为等价类。SAM 中的每个状态对应一个等价类。

引理 $3$ ：对于一个 $p$ ，其对应的子串集合中，较短者一定是较长者的后缀。

也比较显然。

$\operatorname{substr}(p)$ 代表状态 $p$ 可以代表的所有子串集合，
$\operatorname{longest}(p)$ 代表状态 $p$ 所对应的最长子串；
$\operatorname{shortest}(p)$ 代表状态 $p$ 所对应的最短子串；
$\operatorname{len}(p)=|\operatorname{longest}(p)|$ 。

定义状态 $p$ 的后继状态 $\operatorname{link}(p)$ 指向 $\operatorname{longest}(p)$ 最长的一个后缀 $w$ ，满足 $w\not\in \operatorname{substr}(p)$ 。所有的后缀链接形成一棵以 $T$ 为根的有根树，另外有 $|\operatorname{shortest}(p)|=\operatorname{len}(\operatorname{link}(p))+1$ 。

之前给出的图的右侧是一棵后缀链接构成的树。可以发现，如果按照 $\operatorname{endpos}$ 集合构造树，那么构造出来的树是相同的。

模板，求出 endpos 大小和 len 即可，构建 SAM 的代码如下：

#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))

int cnt = 1, las = 1, son[N][S], len[N], fa[N]; 

void ins(char s) {
    int it = s - 'a', cur = ++cnt, p = las; 
    len[cur] = len[p] + 1; las = cur; 
    while (!son[p][it]) son[p][it] = cur, p = fa[p]; 
    if (!p) return fa[cur] = 1, void(); 
    int q = son[p][it]; 
    if (len[q] == len[p] + 1) return fa[cur] = q, void(); 
    int cl = ++cnt; cpy(son[cl], son[q], S); 
    len[cl] = len[p] + 1, fa[cl] = fa[q], fa[q] = fa[cur] = cl; 
    while (son[p][it] == q) son[p][it] = cl, p = fa[p]; 
}

后缀树

广义 SAM

SAM 例题

使用 SAM 解决更为方便。

[SDOI2016] 生成魔咒

Portal.

SAM 上新增一个状态答案会增加 $\operatorname{len}-(\operatorname{minlen}-1)=\operatorname{len}-\operatorname{falen}$ ，开个 map 跑 SAM 即可。代码。

[CF235C] Cyclical Quest