基础字符串算法（字典树、KMP、Z 算法、Manacher、AC 自动机）复习笔记

字典树 Trie

Trie 简介

字典树，就像字典一样，可以插入单词，也可以查询一个单词是否存在。

字典树是一棵外向树。节点编号没有任何意义，只是动态开点得到的，字典树的边上有字母。我们称节点 \(u\) 的字母为 \(c\) 的出边指向的节点为 \(u\) 的 \(c\textrm{-son}\)。每个节点唯一对应了一个前缀，就是从根节点到这个节点的路径上所有边上的字母串起来。

字典树的每一个节点要记录所有儿子和终止标记，终止标记表示这个前缀是否是一个完整的单词，也就是这个节点是否是一个单词的结尾。

例如，对于 \(\{\texttt{zpl},\texttt{zplqwq},\texttt{zplqaq},\texttt{ruier}\}\) 建立的字典树如下：（黄色表示终止标记为真）

\(11\) 号节点表示了前缀 \(\texttt{rui}\)，它不是合法的单词，所以终止标记为假。\(3\) 号节点表示了前缀 \(\texttt{zpl}\)，它是合法的单词，所以终止标记为真。

Trie 的插入操作

我们使用 \(0\) 号节点代表根节点，假设字符集是小写字母，那么我们从根节点开始，枚举字符串的每一个字符，找到对应的儿子。如果不存在这个儿子，就动态开点创建一个。直到遍历完字符串，将停留在的节点的终止标记标为真。

时间复杂度 \(\mathcal{O}(|s|)\)。

Trie 的查询操作

从根节点开始，枚举字符串的每一个字符，找到对应的儿子。如果走到了不存在的节点，则查找失败。如果最后走到的节点的终止标记为假（例如在上图中查找 \(\texttt{rui}\)），也是查找失败。否则查找成功。

时间复杂度 \(\mathcal{O}(|s|)\)。

代码

struct Trie {
    int son[K][26], tag[K], sz;
    Trie() : sz(0) {
        memset(son, 0, sizeof(son));
        memset(tag, 0, sizeof(tag));
    }
    ~Trie() {}
    void insert(char* s, int l) {
        int u = 0;
        rep(i, 0, l-1) {
            int c = s[i] - 'a';
            if(!son[u][c]) son[u][c] = ++sz;
            u = son[u][c];
        }
        ++tag[u];
    }
    int find(char *s, int l) {
        int u = 0;
        rep(i, 0, l-1) {
            int c = s[i] - 'a';
            if(!son[u][c]) return 0;
            u = son[u][c];
        }
        return tag[u];
    }
};

Trie 树的应用

Trie 树上可以跑树形 DP\(^{[1]}\)，也可以用类似虚树的方法进行重构\(^{[2]}\)。

Trie 树还有很重要的应用是 01Trie，可以维护异或相关的操作，例如维护数组中任意两个数的最大异或和\(^{[3]}\)等。当然，Trie 树也可以可持久化\(^{[4]}\)。但是这些都是 Trie 树作为数据结构的应用，鉴于本博客是复习基础字符串算法，就不展开讨论了。

KMP 算法

KMP 简介

KMP 算法是单模式串字符串匹配算法，由 D.E.Knuth、J.H.Morris、V.R.Pratt 提出，是在 Brute Force 基础上的改进。Brute Force 中失配时文本串匹配位置会发生回退，而 KMP 算法充分利用了失配信息，不需要回退，大大提高了效率。

处理前缀 \(\pi\) 函数

我们定义前缀函数 \(\pi(i)\) 表示 \(s_{1\dots i}\) 最长的相等的真前缀和真后缀的长度。特别地，我们规定 \(\pi(1)=0\)。

假设我们已经知道了 \(\pi(1\dots i-1)\)，下面考虑如何求出 \(\pi(i)\)。

第一种情况比较简单，\(s_i=s_{\pi(i-1)+1}\)。

\[ \begin{array}{c:cccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ s & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{c} & \texttt{d} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{c} & \texttt{e} \\ \hline \pi & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 3 & ? & \\ & \bigstar & \bigstar & \bigstar & \vartriangle & & \bigstar & \bigstar & \bigstar & \vartriangle & \\ \end{array} \]

容易发现 \(\pi(i)=\pi(i-1)+1\)。

第二种情况就复杂了，如果 \(s_i\ne s_{\pi(i-1)+1}\)。

\[ \begin{array}{c:ccccccccccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ s & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{d} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{e} & \texttt{z} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{d} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{d} \\ \hline \pi & 0 & 0 & 1 & 0 & 1 & 2 & 3 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ? \\ & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \vartriangle & & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \vartriangle\\ & \bigstar & \bigstar & \bigstar & \vartriangle & \bigstar & \bigstar & \bigstar & \diagup & & \bigstar & \bigstar & \bigstar & \diagup & \bigstar & \bigstar & \bigstar & \vartriangle\\ \end{array} \]

我们发现失配了，怎么办？\(s_{1\dots 8}\ne s_{10\dots 17}\) 匹配失败了，只好匹配一个更短的串。那更短的串长度是多少呢？

还记得前缀 \(\pi\) 函数的意义吗？\(\pi(16)=7\) 使得 \(s_{1\dots 7}=s_{10\dots 16}\)，才可能匹配 \(s_{1\dots 8}\) 和 \(s_{10\dots 17}\)。现在失配了，找下一个前缀等于后缀，我们跳 \(\pi\) 函数。发现 \(\pi(7)=3\)，这意味着 \(s_{1\dots 3}=s_{5\dots 7}\)，又因为 \(\pi(16)=7\) 即 \(s_{1\dots 7}=s_{10\dots 16}\)，根据等号的传递性我们知道 \(s_{1\dots 3}=s_{5\dots 7}=s_{10\dots 12}=s_{14\dots 16}\)，因此 \(s_{1\dots 3}=s_{14\dots 16}\)，即 \(s_{1\dots 4}\) 和 \(s_{14\dots 17}\) 是下一个可能匹配的。那是否匹配呢？发现是的，于是 \(\pi(17)=3+1=4\)。如果不匹配怎么办？很简单，类比刚刚的推导过程继续跳 \(\pi\) 即可。

别看上面说的麻烦，实际上代码很短：（\(t\) 为模式串，\(m\) 为模式串长度，\(nxt\) 是上面的前缀 \(\pi\) 函数）

nxt[1] = 0;
rep(i, 2, m) {
    int j = nxt[i-1];
    while(j && t[i] != t[j+1]) j = nxt[j];
    if(t[i] == t[j+1]) ++j;
    nxt[i] = j;
}

复杂度为 \(\mathcal{O}(m)\)，怎么证明？

水杯容量为 \(m\) 升，初始为空，每次最多加一升水，加不超过 \(m\) 次，每次倒水最少倒一升，最多能倒几次？

\(\pi\) 的取值最大为 \(m\)，初始为 \(0\)，每次最多加一，加不超过 \(m\) 次，每次失配跳 \(\pi\) 最少减一，最多跳多少次 \(\pi\)？

字符串匹配

我们记函数 \(f(i)\) 表示“以 \(i\) 结尾的文本串的后缀”和“模式串的前缀”的最长匹配长度（与前缀 \(\pi\) 函数类似）。

与处理前缀 \(\pi\) 函数类似，尝试用 \(f(1\dots i-1)\) 求出 \(f(i)\)。依然分两种情况，第一种情况答案为 \(f(i-1)+1\)，第二种情况跳前缀 \(\pi\) 函数。发现 \(f(i)\) 只与 \(f(i-1)\) 和前缀 \(\pi\) 函数有关，代码实现可以不写，但我习惯写上。

代码实现类似：（\(s\) 为文本串，\(n\) 为文本串长度，\(t\) 为模式串，\(m\) 为模式串长度，\(nxt\) 是上面的前缀 \(\pi\) 函数）

rep(i, 1, n) {
    int j = f[i-1];
    while(j && s[i] != t[j+1]) j = nxt[j];
    if(s[i] == t[j+1]) ++j;
    f[i] = j;
    if(f[i] == m) printf("%d\n", i-m+1);
}

时间复杂度证明类似。

KMP 的应用

KMP 除了可以进行朴素的单模式串字符串匹配\(^{[5]}\)以外，还有其他的应用，例如建失配树\(^{[6]}\) 求 border 等。

KMP 还可以与矩阵快速幂结合进行 DP\(^{[7]}\)。

Z 算法

Z 算法简介

Z 算法在国内也被称为“扩展 KMP”，但我并不很认同这个叫法。Z 算法只是 \(z\) 函数定义与前缀 \(\pi\) 函数比较像，但是 \(z\) 函数与前缀 \(\pi\) 函数没有什么联系，而且求解过程完全不同，称为“扩展 KMP”完全是先入为主的观念。Z 算法的求解过程相比于 KMP 的跳 \(\pi\) 函数，更像 Manacher 算法的“段内直接求，段外暴力扩展”（后面讲到 Z 算法和 Manacher 算法步骤就明白了），但与 Manacher 求解的问题和代码实现又完全不同。我倾向于认为 Z 算法是一个独立的算法，而不是“扩展 KMP”或“扩展 Manacher”。

Z 算法也是一种字符串匹配算法，但不如 KMP 算法常用，因为 KMP 算法更好写。

处理 Z 函数

在 Z 算法中我们约定字符串下标从 \(0\) 开始。其实是因为老师说他试过从 \(1\) 开始但写挂了，我就没这么干。

我们定义函数 \(z(i)\) 表示 \(s\) 与 \(s_{i\dots n-1}\) 的最长公共前缀（LCP）长度。特别地，\(z(0)=0\)。

注意区分 \(z\) 函数与前缀 \(\pi\) 函数，前缀 \(\pi\) 函数是在 \(1\) 位置向后看、在 \(i\) 位置向前看（取子串但不反向）的最长相等长度，而 \(z\) 函数是在 \(0\) 位置向后看、在 \(i\) 位置也向后看的最长相等长度。

例如 \(z(\texttt{abacaba})=[0,0,1,0,3,0,1]\)。

我们从 \(1\) 到 \(n-1\) 依次计算 \(z(i)\)。

对于 \(i\)，我们称 \([i,i+z(i)-1]\) 为 \(i\) 的匹配段，也称 \(\textrm{Z-box}\)。

我们维护右端点最靠右的匹配段 \([l,r]\)（与后文 Manacher 算法维护的右端点最靠右的回文段类似），则 \(s_{l\dots r}\) 是 \(s\) 的前缀。计算 \(z(i)\) 时有 \(l < i\)，初始 \(l=r=0\)。

第一种情况，\(i\le r\)，那么根据 \(z\) 的定义有 \(s_{i\dots r}=s_{i-l\dots r-l}\)（因为 \(s_{0\dots r-l}=s_{l\dots r}\)），因此有 \(z(i)\ge\min(z(i-l),r-i+1)\)。

这时再分两种小情况。

情况 A，若 \(z(i-l) < r-i+1\)，则 \(z(i)=z(i-l)\)。

\[ \begin{array}{c:cccccccccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ s & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{c} & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{x} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{z} \\ \hline z & 0 & 1 & 0 & 0 & 3 & ? & & & & & & \\ [l,r] & & & & & \bigstar & \bigstar & \bigstar & & & & & \\ \textrm{prefix} & \bigstar & \bigstar & \bigstar & & & & & & & & & \\ i-l,i & & \vartriangle & & & & \vartriangle & & & & & & \\ z(i)=z(i-l) & \vartriangle & \diagup & & & & \vartriangle & \diagup & & & & & \\ \textrm{new }[l,r] & & & & & \bigstar & \bigstar & \bigstar & & & & & \\ \end{array} \]

情况 B，若 \(z(i-l)\ge r-i+1\)，我们令 \(z(i)=r-i+1\)，然后此时 \(i\) 的匹配段可能超过了 \(r\) 的已知部分，我们不知道 \(r+1\) 往后是否还能继续匹配，于是我们需要暴力扩展。

\[ \begin{array}{c:cccccccccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ s & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{c} & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{x} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{z} \\ \hline z & 0 & 1 & 0 & 0 & 3 & 1 & 0 & 0 & 2 & ? & & \\ [l,r] & & & & & & & & & \bigstar & \bigstar & & \\ \textrm{prefix} & \bigstar & \bigstar & & & & & & & & & & \\ i-l,i & & \vartriangle & & & & & & & & \vartriangle & & \\ \textrm{brute force} & \bigstar & \vartriangle & \diagup & & & & & & & \bigstar & \vartriangle & \diagup \\ \textrm{new }[l,r] & & & & & & & & & & \bigstar & \bigstar & \\ \end{array} \]

第二种情况，\(i > r\)，也就是 \(i\) 这个位置都没有被已知部分覆盖到，那我们只能暴力扩展。

\[ \begin{array}{c:cccccccccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ s & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{c} & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{x} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{z} \\ \hline z & 0 & 1 & 0 & 0 & 3 & 1 & 0 & 0 & ? & & & \\ [l,r] & & & & & \bigstar & \bigstar & \bigstar & & & & & \\ \textrm{prefix} & \bigstar & \bigstar & \bigstar & & & & & & & & & \\ \textrm{brute force} & \bigstar & \vartriangle & \diagup & & & & & & \bigstar & \vartriangle & \diagup & \\ \textrm{new }[l,r] & & & & & & & & & \bigstar & \bigstar & & \\ \end{array} \]

得到了 \(i\) 的匹配段之后，如果 \(i+z(i)-1 > r\)，记得更新 \(l,r\)。

最后按解题需要可以把 \(z(0)\) 置成 \(n\)。

实际写代码时我们并不会按第一类 A、第一类 B、第二类分三种情况讨论，而是分两类，因为第一类 B 和第二类都是暴力扩展，可以合并。

参考代码：

z[0] = 0;
ll L = 0, R = 0;
rep(i, 1, m-1) {
    if(i <= R && R - i + 1 > z[i-L]) z[i] = z[i-L];
    else {
        z[i] = max(R-i+1, 0LL);
        while(i + z[i] < m && t[z[i]] == t[i+z[i]]) ++z[i];
    }
    if(i + z[i] - 1 > R) {
        L = i;
        R = i + z[i] - 1;
    }
}
z[0] = m;

时间复杂度为 \(\mathcal{O}(m)\)，怎么证明？

\(R\) 单调不降，每次暴力只会从 \(R\) 开始向右找，且会更新 \(R\)。每个位置只会被暴力到一次，均摊 \(\mathcal{O}(m)\)。

字符串匹配（求 LCP）

只求模式串每个后缀和模式串本身的 LCP 不够强，还需要求文本串每个后缀和模式串的 LCP。

我们可以类似地定义一个 \(p\) 函数，仿照上面分类讨论，代码如下：

L = 0; R = 0;
rep(i, 0, min(m, n)-1) { // 暴力求出 p[0]
    if(s[i] == t[i]) ++p[0];
    else break;
}
bool tmp = 0;
if(tmp = (p[0] == n)) p[0] = 0;
rep(i, 1, n-1) {
    if(i <= R && R - i + 1 > z[i-L]) p[i] = z[i-L];
    else {
        p[i] = max(R-i+1, 0LL);
        while(i + p[i] < n && t[p[i]] == s[i+p[i]]) ++p[i];
    }
    if(i + p[i] - 1 > R) {
        L = i;
        R = i + p[i] - 1;
    }
}
if(tmp) p[0] = n;

时间复杂度证明类似。

Z 算法的应用

Z 算法解决的问题与 KMP 算法较为类似，应用也大体一样，不再列出。

Manacher 算法

Manacher 简介

Manacher 算法常用于解决字符串的回文相关问题。

预处理字符串

我们注意到回文分为两种——奇回文（如 \(\texttt{ABCDCBA}\)）和偶回文（如 \(\texttt{ABCCBA}\)）。

分开处理太麻烦了，我们预处理一下字符串，使得只需要考虑奇回文。

具体做法就是在字符串的每个字符之间插入一些符号，例如 \(\texttt{ABCCBABBCC}\to\texttt{^|A|B|C|C|B|A|B|B|C|C|\$}\)。注意开头和结尾要插入两个不同字符。这样的作用是，这个串中，中心是 \(\texttt{|}\) 的回文串对应了原串的偶回文，否则对应了原串的奇回文。

处理半径函数

半径函数好像没有特别统一的字母，比如我就用的 \(a\)。\(a_i\) 表示以 \(i\) 为中心的最长的回文串的半径长度，也就是向左/右扩展的步数。容易发现回文串的实际长度为 \(2a_i-1\)，又因为最两边一定是字符 \(\texttt{|}\)，中间是分隔符和原串字符交替，故原串中对应的回文串长度为 \(a_i-1\)。

我们考虑如果知道了 \(a_{1\dots i-1}\)，怎么求出 \(a_i\)。我们需要维护两个变量 \(m,j\)，\(j\) 是目前已知的所有回文串中最靠右的右侧端点的位置，\(m\) 是这个最靠右的回文串的中心。类似于 Z 算法，我们进行分类讨论。

第一种情况，如果 \(i\le j\)，则根据中点公式我们知道 \(i\) 的在 \(m\) 为中心的回文串的对称点为 \(2m-i\)，因为是回文串所以 \(a_i\) 可以根据 \(a_{2m-i}\) 进行更新。需要注意的是，由于 \(j\) 右侧还未知，所以不能简单地 \(a_i\gets a_{2m-i}\)，右端点只能确定到 \(j\) 即 \(a_i\gets\min(a_{2m-i},j-i+1)\)。后面的部分我们暴力。

\[ \begin{array}{c:ccccccccccccccccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ s & \texttt{^} & \texttt{|} & \texttt{c} & \texttt{|} & \texttt{b} & \texttt{|} & \texttt{a} & \texttt{|} & \texttt{b} & \texttt{|} & \texttt{c} & \texttt{|} & \texttt{d} & \texttt{|} & \texttt{c} & \texttt{|} & \texttt{b} & \texttt{|} & \texttt{a} & \texttt{|} & \texttt{c} & \texttt{|} & \texttt{\$} \\ \hline a & 1 & 1 & 2 & 1 & 2 & 1 & 6 & 1 & 2 & 1 & 2 & 1 & 8 & 1 & 2 & 1 & 2 & 1 & ? & & & & \\ [2m-j,j] & & & & & & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \blacktriangle & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & & & \\ 2m-i,i & & & & & & & \vartriangle & & & & & & & & & & & & \vartriangle & & & & \\ \textrm{palindrome} & & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & \blacktriangle & \bigstar & \bigstar & \bigstar & \bigstar & \bigstar & & & & & \diagup & \bigstar & \vartriangle & \bigstar & \diagup & & \\ \end{array} \]

（表格咋还溢出了，可以右键改一下 MathJax 设置然后看）

第二种情况，如果 \(i > j\)，直接暴力就好了。

记得如果需要就更新 \(m,j\)。

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e6+5;

int n, a[N];
char s[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
void read() {
    s[++n] = '^';
    s[++n] = '|';
    char c = getchar();
    for(;!isalpha(c);c=getchar());
    for(;isalpha(c);c=getchar()) {
        s[++n] = c;
        s[++n] = '|';
    }
    s[++n] = '$';
}

int main() {
    read();
    for(int i=1,j=0,m=0;i<=n;i++) { // i : now; j : max right; m : mid;
        if(i <= j) a[i] = min(a[m*2-i], j-i+1);
        for(;s[i-a[i]]==s[i+a[i]];++a[i]);
        if(i + a[i] - 1 >= j) {
            j = i + a[i] - 1;
            m = i;
        }
    }
    rep(i, 3, n-2) printf("%d%c", a[i]-1, " \n"[i==n-2]);
    return 0;
}

时间复杂度证明类似于 Z 算法，考虑 \(j\) 单调不降，只暴力 \(> j\) 部分。

Manacher 的应用

最基础的就是回文串长度\(^{[9]}\)了。（为啥上角标到 \(9\) 了？因为 \(8\) 被暂时隐藏了）

还可能有一些有关回文串的高级要求\(^{[10]}\)\(^{[11]}\)。

还可能重定义一下“回文”\(^{[12]}\)。

AC 自动机

AC 自动机简介

AC 自动机（Aho-Corasick Automaton [???t?m?t?n]）是一种多模式串字符串匹配算法。

需要的前置知识：Trie、KMP。

正常来讲还需要一个前置知识“自动机”，但本文不会涉及过多的“自动机”相关内容，因此不学应该没有关系。如果学了自动机，可以对照着自动机的定义看一看 ACAM 中哪些部分属于自动机，哪些部分不属于。

建立 Trie 树

首先需要把所有模式串插到 Trie 树中，详见上面的【字典树】部分。

类似于 Trie 树每个节点的意义（即一个前缀），在 AC 自动机的 Trie 树（和后文会提到的 Trie 图）中，每一个节点都代表了一个“状态”，状态可视作一个前缀。

我们定义所有状态的集合为 \(Q\)，也可以视作 Trie 树（Trie 图）所有节点的集合。

fail 指针定义

fail 指针，即失配指针，用来辅助多模式串的匹配。

状态 \(u\) 的 fail 指针会指向另一个状态 \(v\)（\(u,v\in Q\)），满足 \(v\) 是 \(u\) 的最长的 \(\in Q\) 的真后缀。

举个例子，对于模式串为 \(\{\texttt{i},\texttt{he},\texttt{his},\texttt{she},\texttt{hers}\}\) 来讲，构建出的 Trie 树如下：

\(0\sim 10\) 号点对应的状态分别是：\(\varnothing,\color{red}{\texttt{i}},\texttt{h},\color{red}{\texttt{he}},\texttt{hi},\color{red}{\texttt{his}},\texttt{s},\texttt{sh},\color{red}{\texttt{she}},\texttt{her},\color{red}{\texttt{hers}}\)。注意到我们标红的这些状态在 Trie 树中是终止节点，也就是说是合法的模式串，这些状态我们称为“接受状态”，它们构成集合 \(F\)，显然 \(F\subseteq Q\)。

那么 fail 指针具体是怎么指的呢？我们以状态 \(\color{red}{\texttt{hers}}\) 为例，在状态集合 \(Q\) 中存在的最长的 \(\color{red}{\texttt{hers}}\) 的真后缀为 \(\texttt{s}\)，所以 \(10\) 号点的 fail 指针指向 \(6\) 号点。同理，\(\color{red}{\texttt{she}}\) 的最长在 \(Q\) 中的真后缀为 \(\color{red}{\texttt{he}}\)，所以 \(8\) 号点的 fail 指针指向 \(3\) 号点。

类似地，我们把所有 fail 指针都画出来，就得到了下面这张图：

其中红色边就是 fail 指针。

我个人感觉 fail 指针跟 KMP 中的前缀 \(\pi\) 函数类似，只不过前缀 \(\pi\) 函数指的是自己内部的最长 border（后缀等于前缀），而 fail 指针指的是所有模式串的所有状态的最长 border。

fail 指针构建的基础思想

强调：这里是基础思想，也就是 fail 指针建立要明白的思想，但实际写代码我们不会这么写。

fail 指针采用 bfs 的方式进行建立，不支持动态插串。

我们假设所有深度小于 \(u\) 深度的节点的 fail 指针都已求得，下面来求 \(u\) 的 fail 指针。假设 \(u\) 是 \(p\) 的 \(c\textrm{-son}\)，也就是 \(p\) 通过字母 \(c\) 边指向 \(u\)。

1. 如果 \(\textrm{fail}(p)\) 有 \(c\textrm{-son}\)，则把 \(u\) 的 fail 指向它（这个儿子）。类似于 KMP 算法中 \(s_i=s_{\pi(i-1)+1}\)，这里的意思就是在 \(p\) 和 \(\textrm{fail}(p)\) 后面都加上一个字符 \(c\)（是 \(c\) 不是 \(\texttt{c}\)），对应着 \(u\) 和 \(\textrm{fail}(u)\)。
2. 如果 \(\textrm{fail}(p)\) 没有 \(c\textrm{-son}\)，我们找到 \(\textrm{fail}(\textrm{fail}(p))\)，重复步骤 \(1,2\) 判断是否有 \(c\textrm{-son}\)，一直跳 fail 指针直到根节点。类似于 KMP 算法中的跳 \(\pi\) 函数的过程。
3. 如果一直都没有，就意味着 \(u\) 的所有真后缀都不在状态集合 \(Q\) 中（即不在 Trie 树中），让 fail 指针指向根节点也就是空串 \(\varnothing\)。

如此完成 \(\textrm{fail}(u)\) 的构建。

再放一遍上面那张图，可以手玩一下这个过程，推几个 fail 指针试试：

Trie 图与自动机的构建

Trie 图，即字典图，会在 Trie 树的基础上添加一些辅助边，构建出完整的自动机。

在 Trie 图中添加的这些边与 Trie 树（外向树）中的父子关系是等效的，一般不会区分。

Trie 树中的父子关系 \({son}_{u,c}\)（即 \(u\) 的 \(c\textrm{-son}\)）还会被保留，在 Trie 图中会多出一些“父子关系”。这里“父子关系”的意义被扩展了，\({son}_{u,c}\) 是在状态 \(u\) 后添加一个字母 \(c\) 转移到的状态，也就是自动机中的转移函数 \(\delta(u,c)\)。

下面结合代码讲解：

void build() {
    queue q;
    rep(i, 0, 25) if(son[0][i]) q.push(son[0][i]);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        rep(i, 0, 25) {
            if(son[u][i]) {
                fail[son[u][i]] = son[fail[u]][i];
                q.push(son[u][i]);
            }
            else son[u][i] = son[fail[u]][i];
        }
    }
}

其中 \(0\) 是 Trie 树的树根。你可能会懵掉：上面的基础思想怎么完全不见了？别着急，我们慢慢讲。

\(0\) 的 fail 指针指向 \(0\)，不用处理。因为 \(0\) 的所有儿子的 fail 指针根据定义也应该指向 \(0\)，所以我们把它们入队而不是把 \(0\) 入队。如果这里把 \(0\) 入队，根据下面的 bfs 代码，\(0\) 的儿子的 fail 指针将指向自己，会挂掉。

然后开始 bfs，取出队首元素 \(u\)，枚举 \(u\) 的所有儿子。此时深度不超过 \(u\) 深度的节点的 fail 指针都已经求出。

1. 如果 \({son}_{u,c}\) 存在，根据上面的思想，\(\textrm{fail}({son}_{u,c})\gets{son}_{\textrm{fail}(u),c}\)（等量代换 \(u\to p\)，\({son}_{u,c}\to u\) 就是上面基础思想中的第一种情况）。
2. 如果 \({son}_{u,c}\) 不存在（即 \({son}_{u,c}=0\)，这里 \(0\) 是不合法的意思而不是根节点），我们需要跳 fail 指针。正常来讲我们需要使用 while 循环向上不断跳 fail，但此时我们并不需要。我们可以直接改掉 \({son}_{u,c}\) 的值，把 \(\delta(u,c)\)（也就是状态 \(u\) 后面接字符 \(c\)）转移到一个合法的节点去。由于更浅的节点的 fail 都已经链接好，我们可以直接让 \(\delta(u,c)\) 转移到 \(\textrm{fail}(u)\) 的 \(c\textrm{-son}\) 去。我们不需要一个 \(\delta\) 函数，可以直接在 \(son\) 里面改，也就是改变了 Trie 树的形态，让它不再是树了，这也是 Trie 图名字的由来。

好了，说了这么多，让我们来见识一下 Trie 图长啥样吧！！！11

下面的图中黑色边代表 Trie 树边，红色边代表 fail 指针，蓝色边代表 Trie 图除了 Trie 树以外的边。

首先将 \(1,2,6\) 入队，它们的 fail 指向 \(0\)。

取出队首元素 \(1\)（实际上因为按字母顺序枚举所以会先取 \(2\)，不过差不多），连 \(1\) 的 Trie 图：

取出队首元素 \(2\)，连 \(2\) 的 Trie 图和儿子的 fail，把儿子 \(3,4\) 入队：

取出队首元素 \(6\)，连 \(6\) 的 Trie 图和儿子的 fail，把儿子 \(7\) 入队：

于是第一层我们就连完了。

强烈建议手玩一下第一层的连边，最好动手画一画，因为后面就手玩不了了！！1

后面就不这么详细地说了，连完第二层是这样的：

连完第三层是这样的：

全连完是这样的：

这并不是全部，还有几百条边被我省略了。有些节点的有些字母没有出边，实际上也是有边的，它们全部连向 \(0\)。

Trie 图的所有边（黑边和蓝边）构成了 AC 自动机，注意 fail 指针（红边）不属于 AC 自动机，只是用来辅助求解。

自动机上边的意义

说了这么多，自动机上边的意义是什么呢？

AC 自动机的初始状态为 \(0\) 即空串 \(\varnothing\)，可看做一个人初始站在 \(0\) 处。

这个人每次接受一个字母作为指令，并相应地移动。

例如，我给她一个指令 \(\texttt{s}\)，她就会按照我的要求，找到当前所在节点（状态）的标有字母 \(\texttt{s}\) 的出边（转移），移动到出边指向的节点（状态），也就是说会执行 \(0\stackrel{\texttt{s}}{\to}6\)。我再给她一个指令 \(\texttt{h}\)，她就会转移 \(6\stackrel{\texttt{h}}{\to}7\)。这部分都比较好理解，因为先后接收了 \(\texttt{sh}\)，就会走到 \(\texttt{sh}\) 的状态。

但是如果再给一个指令 \(\texttt{h}\)，此时沿着蓝边转移 \(7\stackrel{\texttt{h}}{\to}2\) 到了状态 \(\texttt{h}\) 是什么意思呢？

此时接收到了指令 \(\texttt{shh}\)，但没有状态 \(\texttt{shh}\)，而是到了状态 \(\texttt{h}\)。这个 \(\texttt{h}\) 就是 \(\texttt{shh}\) 在状态集合 \(Q\) 中的最长后缀。也就是说，走若干步后会停在状态集合 \(Q\) 中最长后缀的位置。

发现什么没？这个比较类似 KMP 的匹配过程。KMP 匹配时如果文本串当前字符与模式串匹配到的字符相等，就会把匹配长度加一（也就是我定义的 \(f\) 函数执行 \(f(i)=f(i-1)+1\)），对应了 AC 自动机中的“走黑边”，都是把深度加一；如果发生失配，就会跳 \(\pi\) 函数，一直跳下一个的 border 进行匹配，更新匹配长度为最长的“‘当前文本串匹配到的位置’的后缀和模式串的前缀匹配（border）”长度，对应了 AC 自动机中的“走蓝边”，都是停留在最长的后缀等于前缀的位置。

那么如果我再给一个指令 \(\texttt{e}\)，此时转移 \(2\stackrel{\texttt{e}}{\to}\color{red}{3}\)，转移到了一个接受状态（也就是一个完整的模式串）\(\texttt{he}\)，意味着什么呢？此时的指令 \(\texttt{shhe}\) 匹配了一个模式串 \(\color{red}{\texttt{he}}\)。

如果我们清空所有，回到初始状态给三个指令 \(\texttt{she}\)，会走到 \(8\) 的位置，是一个接受状态，是不是只意味着匹配了一个模式串 \(\color{red}{\texttt{she}}\) 呢？并不是，你应该发现了 \(\texttt{she}\) 同样可以匹配 \(\color{red}{\texttt{he}}\)。此时怎么处理？这个时候我们的 fail 指针（红边）就派上用场了，我们沿着 fail 指针向上跳到根（开临时变量跳，小人依然站在 \(\color{red}{\texttt{she}}\) 的位置），把路径上遇到的所有接受状态都匹配上。

这是最暴力的办法，多数情况无法保证复杂度。如果只要求每个模式串是否出现\(^{[13]}\)是可以这么做，然后把终止标记改成 \(-1\)，后面遇到 \(-1\) 就不跳，均摊是正确的。但是出现多少次\(^{[14]}\)\(^{[15]}\)是做不了的（上角标 \(14\) 确实可以水过，但复杂度是错的，只是洛谷数据水没卡掉），此时可能需要在 fail 树（失配树）上做接受状态标记的前缀和来维护。

这是上角标 \(13\) 的完整代码：

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e6+5;

int n;
char s[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
struct ACAM {
    int tot, son[N][26], fail[N], tag[N];
    void insert(char* s, int len) {
        int u = 0;
        rep(i, 0, len-1) {
            int c = s[i] - 'a';
            if(!son[u][c]) son[u][c] = ++tot;
            u = son[u][c];
        }
        ++tag[u];
    }
    void build() {
        queue q;
        rep(i, 0, 25) if(son[0][i]) q.push(son[0][i]);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            rep(i, 0, 25) {
                if(son[u][i]) {
                    fail[son[u][i]] = son[fail[u]][i];
                    q.push(son[u][i]);
                }
                else son[u][i] = son[fail[u]][i];
            }
        }
    }
    int query(char* s, int len) {
        int u = 0, ans = 0;
        rep(i, 0, len-1) {
            int c = s[i] - 'a';
            u = son[u][c];
            for(int v=u;v&&tag[v]!=-1;v=fail[v]) {
                ans += tag[v];
                tag[v] = -1;
            }
        }
        return ans;
    }
}AC;

int main() {
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%s", s);
        AC.insert(s, strlen(s));
    }
    AC.build();
    scanf("%s", s);
    printf("%d\n", AC.query(s, strlen(s)));
    return 0;
}

AC 自动机的应用

除了上面上角标 \(13,14,15\) 的基础字符串匹配问题以外，还可以解决很多其它问题，例如 AC 自动机上的搜索\(^{[16]}\)，以及 AC 自动机上 DP\(^{[17]}\)等。