字符串一家子

$s _ {[l,r]}$ 指 $s$ 中区间 $[l,r]$ 构成的子串。

0. 字符串哈希

原理不再赘述，尽量选几个不常见的模数与底数，实在不行多哈希几次。

还有和哈希不要用，用一个卡一个。

顺手提一个基本不会被卡的哈希，splitmix64，实现如下：

1
inline uint64_t splitmix64(uint64_t x)
2
{
3
    x += 0x9e3779b97f4a7c15;
4
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
5
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
6
    return x ^ (x >> 31);
7
}

这几个 magic number 太难记了怎么办？随机数也可以，改了之后就是这样：

1
mt19937_64 rnd(random_device{}());
2
inline uint64_t splitmix64(uint64_t x)
3
{
4
    const static uint64_t r1 = rnd(),r2 = rnd(),r3 = rnd();
5
    x += r1;
6
    x = (x ^ (x >> 30)) * r2;
7
    x = (x ^ (x >> 27)) * r3;
8
    return x ^ (x >> 31);
9
}

1. KMP

主要是用来算前缀的最长 Border，Border 指相同的前后缀，即 $s _ {[1,i]} = s _ {}$ 。

主要思想就是如果发生失配，我们可以把前缀移到最长的相等后缀处，减少匹配次数。记 $kmp _ i$ 表示 $s _ {[1,i]}$ 的最长 Border 长度，则我们考虑用类似 DP 的方式来做：

对于一个 $i$ ，我们考虑扩展 $kmp _ {i - 1}$ ，如果 $s _ i = s _ {kmp _ {i - 1} + 1}$ ，那我们就可以直接扩展 $kmp _ {i - 1}$ ，即 $kmp _ i \gets kmp _ {i - 1} + 1$ 。

如果失配，我们考虑求 $kmp$ 是为了干什么，就是为了解决失配问题，所以我们可以直接利用这个 $kmp$ 来跳，每次，直到跳到一个 $j$ ，使得 $s _ {j + 1} = s _ i$ ，或者 $j$ 变为 $0$ 。然后，这一段的前缀和后缀就匹配了，就可以向上面那样做了。

写成代码是这样的：

1
int kmp[];
2
inline void initKMP(string T)
3
{
4
    int n = T.length();
5
    T = ' ' + T;
6
    for(int i = 2,j = 0;i <= n;i++)
7
    {
8
        while(j && T[j + 1] != T[i])
9
            j = kmp[j];
10
        if(s[j + 1] == s[i])
11
            ++j;
12
        kmp[i] = j;
13
    }
14
}

匹配应该不怎么常考，但还是和上面类似，区别就是匹配长度为 $|T|$ 的时候记录一下匹配，代码在下面。

1
int kmp[];
2
inline void initKMP(string& T);
3
inline void query(string &S)
4
{
5
    int n = T.length(),m = S.length();
6
    for(int i = 1,j = 0;i <= m;i++)
7
    {
8
        while(j && T[j + 1] != S[i])
9
            j = kmp[j];
10
        if(T[j + 1] == S[i])
11
            ++j;
12
        if(j == n)
13
            // Matched
14
    }
15
}

求最小循环周期

对于一个字符串，其最小循环周期长度为 $n - kmp _ {n}$ ，如果可以整除，则 $S$ 可以被长为 $n - kmp _ n$ 的字符串 $T$ 循环表示，否则 $S$ 是 $T$ 拼接若干次的一个子串。

KMP 自动机

可以认为是单串的 ACAM。

和 ACAM 一样，有个 Fail 指针，但是我们没必要像 ACAM 那样建。我们定义 $\delta(i,j)$ 为第 $i$ 位，字符为 $j$ 的转移，则有 $\delta(i,j) = \begin{cases} i&j = s _ {i + 1} \\ \delta(fail _ {i},j)&j \neq s _ {i + 1} \end{cases}$ 。

发现每一次的更新都是复制一个数组再进行单点修改，所以对于较大的字符集可以用可持久化区间树来建。对于每个点，Fail 指向的点的深度就是这个前缀的最长 Border 长度。

exKMP / Z 函数

我们设一个字符串的 Z 函数 $z _ i$ 为 $S$ 与 $S _ {[i,n]}$ 的 LCP 长度。

对于 $z _ 1$ ，显然为 $n$ 。否则，上面的等价于 $S$ 与 $S _ {[i,n]}$ 的最长公共子串长度，我们可以维护一个 $l,r$ 表示 $s _ {[l,r]}$ 是一个匹配的最长公共子串，对于一个 $i$ ，若 $i \le r$ ，则 $z _ i = \min \{ z _ {i - l + 1},r - i + 1 \}$ 。

然后我们暴力扩展，如果最后 $i$ 超过了 $r$ ，更新 $l,r$ 。

类似于 KMP，我们也可以求出 $T$ 与 $S$ 的每一个后缀的 LCP 长度，记为 $p$ ，则和上面类似，若 $i \le r$ ，有 $p _ i = \min \{ z _ {i - l + 1},r - i + 1 \}$ ，随后暴力扩展，更新边界。

代码如下：

1
string S,T;
2
int n,m,z[MAXN],p[MAXN];
3
inline void initZFunc()
4
{
5
    z[1] = n;
6
    for(int i = 2,l = 0,r = 0;i <= n;i++)
7
    {
8
        if(i <= r)
9
            z[i] = min(z[i - l + 1],r - i + 1);
10
        while(i + z[i] <= n && T[i + z[i]] == T[z[i] + 1])
11
            ++z[i];
12
        if(i + z[i] - 1 > r)
13
            l = i,r = i + z[i] - 1;
14
    }
15
}
16
inline void exKMP()
17
{
18
    initZFunc();
19
    for(int i = 1,l = 0,r = 0;i <= m;i++)
20
    {
21
        if(i <= r)
22
            p[i] = min(z[i - l + 1],r - i + 1);
23
        while(i + p[i] <= m && S[i + p[i]] == T[p[i] + 1])
24
            ++p[i];
25
        if(i + p[i] - 1 > r)
26
            l = i,r = i + p[i] - 1;
27
    }
28
}

2. AC 自动机

用来做多串匹配的东西。

我们考虑用 Trie 来维护多字符串的结构。由于 Trie 的结构我们已经维护了前缀信息，我们只要考虑怎么维护后缀信息就能维护子串信息了。所以我们定义 Fail 指针， $fail _ u$ 指向与从根结点到 $u$ 形成的字符串中有最长公共后缀的且深度低于 $u$ 的结点。然后将 Trie 的 $son(u,c)$ 转换成 $\delta(u,c)$ ，就是原来有的不动他，否则 $\delta(u,c) = \delta(fail _ u,c)$ ，同时可以维护 Fail，若有 $son(u,c) = v$ ，则有 $fail _ v = \delta(fail _ u,c)$ 。

然后字符串匹配的话，我们就在将模式串插入 ACAM 的时候打标记，然后匹配的时候将文本串放到 ACAM 上走，走到一个点，我们跳 Fail，因为 Fail 是最长的后缀，可能有不是最长的后缀匹配上了。

我们发现 Fail 形成一棵树，而匹配的过程就是对于一个点 $u$ 求出到根结点路径上的某些信息，这启发我们直接对 Fail 建树，然后跑树剖或者 DFS 序之类的算法。

ACAM + DS

主要就是从 Fail 树上看。

匹配的实质是 Trie 图的一条路径上所有点的 Fail 树上的祖先权值和，所以对于每一个点在建 Fail 的时候加上父亲的权值。

如果是动态删增字符串的话可以处理出 DFS 序之后用树状数组或线段树维护，如果强制在线可以考虑二进制分组后重构。

ACAM + DP

这种 DP 比较套路，设 $dp _ {i,u}$ 表示考虑长为 $i$ 的字符串，在 ACAM 上的点 $u$ 的某种值，转移就是枚举转移到哪个点。

然后这个可以套上各种通用优化。

3. Manacher

首先给两个相邻字符间加上一个特殊字符，首尾也要加，这样可以减去奇偶性的讨论。

我们考虑对每个位置求出一个回文半径 $p$ ，表示 $s _ {[i - p _ i + 1,i + p _ i - 1]}$ 是一个回文串，像 exKMP 那样，我们维护 $mid,r$ 表示目前维护的回文区间为 $[l,r]$ ，中点为 $mid$ 。

对于一个 $i$ ，若有 $i \le r$ ，则将 $p _ i$ 设为对称点的 $p$ ，即 $p _ i = \min \{ p _ {2mid - i},r - i + 1 \}$ ，然后暴力扩展，随后若超出边界则重新维护 $mid,r$ 。

4. 子序列自动机

顾名思义就是解决子序列有关问题的自动机。

转移函数 $\delta(u,c)$ 表示从 $u$ 开始往后的第一个字符 $c$ 的位置，没有则为一个虚点，可以维护为 $n + 1$ 。我们可以从后往前建自动机，初始先将每个 $\delta(n + 1,c)$ 设为 $n + 1$ ，然后从 $n$ 到 $1$ ，复制 $\delta(i + 1)$ 后将 $\delta(i,s _ i)$ 设为 $i$ 。因为只有复制和单点修改所以字符集较大时同样可以用可持久化区间树来优化。

匹配子序列就可以将文本串放到子序列自动机上，每次走下一个，最后不在 $n + 1$ 就是一个子序列。

Thanks for reading!

字符串一家子

2025 11月 06 周四

2005 字 · 10 分钟

算法学习笔记 OI 字符串