AC 自动机=自动 AC 机？

字符串入门

计算机学院 21 级 何丰辰

视频讲解

字符串入门

---

1. 写在前面

1.1 简介

自动机是 OI、计算机科学中被广泛使用的一个数学模型，其思想在许多字符串算法中都有涉及，因此在学习一些字符串算法前先完成自动机的学习将有助于理解上述算法。本文将由浅入深介绍自动机的基础概念并讲解三种常用的自动机：Trie、KMP 和 AC 自动机。

1.2 前置知识

1.2.1 字符集

一个 字符集 $\sum$ 是一个建立了全序关系的集合，也就是说，$\sum$ 中的任意两个不同的元素 $\alpha$ 和 $\beta$ 都可以比较大小，要么 $\alpha<\beta$，要么 $\beta<\alpha$。字符集 $\sum$ 中的元素称为字符。

1.2.2 字符串

一个 字符串 $S$ 是将 $n$ 个字符顺次排列形成的序列，$n$ 称为 $S$ 的长度，表示为 $|S|$。$S$ 的第 $i$ 个字符表示为 $S[i]$ 或 $S[i-1]$。

1.2.3 子串

字符串 $S$ 的 子串 $S[i \cdots j]，i \leq j$，表示 $S$ 串中从 $i$ 到 $j$ 这一段，也就是顺次排列 $S[i],S[i+1],\cdots,S[j]$ 形成的字符串。

有时也会用 $S[i \cdots j]，i>j$ 来表示空串。

1.2.4 子序列

字符串 $S$ 的 子序列 是从 $S$ 中将若干元素提取出来并不改变相对位置形成的序列，即 $S[p_1],S[p_2],\cdots,S[p_k]，1 \leq p_1<p_2<\cdots<p_k \leq |S|$。

1.2.5 后缀

1.2.5.1 后缀

后缀 是指从某个位置 $i$ 开始到整个字符串末尾结束的一个特殊子串。字符串 $S$ 的从 $i$ 开头的后缀表示为 $Suffix(S,i)$，也就是 $Suffix(S,i)=S[i \cdots |S|-1]$。

1.2.5.2 真后缀

真后缀 指除了 $S$ 本身的 $S$ 的后缀。

1.2.6 前缀

1.2.6.1 前缀

前缀 是指从字符串首开始到某个位置 $i$ 结束的一个特殊子串。字符串 $S$ 的以$i$ 结尾的前缀表示为 $Prefix(S,i)$，也就是 $Prefix(S,i)=S[0 \cdots i]$。

1.2.6.2 真前缀

真前缀 指除了 $S$ 本身的 $S$ 的前缀。

1.2.7 字典序

字典序 指以第 $i$ 个字符作为第 $i$ 关键字进行大小比较，空字符小于字符集内任何字符（即：$a<aa$）。

1.2.8 回文串

回文串 是正着读和倒着读都相同的字符串，即满足 $\forall 1 \leq i \leq |s|，s[i]=s[|s|+1-i]$ 的 $s$。

---

2. 什么是自动机

2.1 自动机的概念

自动机是一个对 信号序列 进行 判定 的数学模型。

• “信号序列”指一连串有顺序的信号，例如字符串从前到后的每一个字符、数组从 1 到 n 的每一个数、数从高到低的每一位等
• “判定”指针对某一命题给出或真或假的回答

需要注意的是：自动机既不是算法，也不是数据结构。因此，实现同一个自动机的方法可能有很多种。

2.2 自动机的分类

• DFA(Deterministic Finite Automaton, 确定有限状态自动机)
• NFA(Nondeterministic Finite Automata, 非确定自动机)

在 OI 中所说的“自动机”一般都指 DFA，即“确定有限状态自动机”。

2.3 自动机的应用案例

• 判定一个二进制数是奇数还是偶数
• 判定一个字符串是否回文
• 判定一个字符串是不是某个特定字符串的子序列等等

因此，自动机常用于解决与字符串相关的问题：

• 字符串匹配问题
• 子串相关问题
• 前缀/后缀相关问题
• 回文串相关问题
• 子序列相关问题

---

3. 常用自动机

3.1 Trie

3.1.1 什么是 Trie

Trie 又名字典树，顾名思义，就是一个像字典一样的树。

3.1.2 Trie 的作用

Trie 是一种能够高效地存储和查找字符串集合的数据结构。

3.1.3 Trie 的理论实现

Trie 的结构很简单，我们用 $\delta(u,c)$ 表示结点 $u$ 的 $c$ 字符指向的下一个结点，或者说是结点 $u$ 代表的字符串后面添加一个字符 $c$ 形成的字符串的结点。

需要注意的是：$c$ 的取值范围和字符集大小相关，不一定是 $0\sim26$。

有时需要标记插入进 Trie 的是哪些字符串，每次插入完成时在这个字符串所代表的结点处打上标记即可。

3.1.4 Trie 的代码实现

结构体封装的 Trie 模板：

struct trie{
    int son[100010][256],cnt[100010]={0},idx;

    void insert(char str[]) { // 插入字符串
        int p=0; // 从根节点开始
        for(int i=0;str[i];i++){ // 遍历字符串
            int u=str[i]; // 当前字符的ASCII码值
            if(!son[p][u])son[p][u]=++idx; // 如果结点不存在就创建
            p=son[p][u]; // 进入下一个结点
        }
        cnt[p]++;
    }
    bool find(char str[]){ // 查找字符串
        int p=0;
        for(int i=0;str[i];i++){
            int u=str[i];
            if(!son[p][u])return 0;
            p=son[p][u];
        }
        return cnt[p];
    }
};

3.2 KMP 算法

3.2.1 什么是 KMP 算法

KMP 是由 Knuth、Pratt 和 Morris 在 1977 年共同发布的一个算法。

3.2.2 KMP 算法的作用

KMP 算法能够高效地进行单模式匹配（即在文本串 $S$ 中查找模式串 $P$）。

3.2.3 单模式匹配的朴素做法

对于在文本串 $s$ 中查找模式串 $p$ 位置的问题（即单模式匹配），我们最先想到的是通过双重循环实现，外层循环遍历 $s$ 的每一个下标，内层循环遍历 $p$ 的每一个下标，依次进行比较即可。

代码实现如下：

// find p[] in s[]
for(int i=1;s[i];i++){
    bool flag=true;
    for(int j=1;p[j];j++){
        if(s[i+j-1]!=p[j]){
            flag=false;
            break;
        }
    }
}

该算法的时间复杂度为 $O(nm)$，当数据范围稍大时就会超时，那么我们如何优化呢？通过 KMP 算法可以大大优化时间复杂度，在介绍 KMP 算法之前，我们需要先了解 前缀函数 的知识。

3.2.4 什么是前缀函数

给定一个长度为 $n$ 的字符串 $s$，其 前缀函数 被定义为一个长度为 $n$ 的数组 $\pi$。其中 $\pi[i]$ 的定义是：

1. 如果子串 $s[0 \cdots i]$ 有一对相等的真前缀与真后缀：$s[0 \cdots k-1]$ 和 $s[i-(k-1) \cdots i]$，那么 $\pi[i]$ 就是这个相等的真前缀（或真后缀）的长度，也就是 $\pi[i]=k$；
2. 如果不止有一对相等的，那么 $\pi[i]$ 就是其中最长的那一对的长度；
3. 如果没有相等的，那么 $\pi[i]=0$。

简单来说 $\pi[i]$ 就是，子串 $s[0 \cdots i]$ 最长相等的真前缀与真后缀的长度。

用数学语言描述如下：

$$\pi[i]=\max_{k=0 \cdots i}\{k:s[0 \cdots k-1]=s[i-(k-1) \cdots i]\}$$

特别的，$\pi[0]=0$。

举例来说，对于字符串 cococola，

$\pi[0]=0$，因为 c 没有真前缀和真后缀，根据规定为 0

$\pi[1]=0$，因为 co 没有相等的真前缀和真后缀

$\pi[2]=1$，因为 coc 相等的真前缀和真后缀只有 c，长度为 1

$\pi[3]=2$，因为 coco 相等的真前缀和真后缀只有 co，长度为 2

$\pi[4]=3$，因为 cococ 相等的真前缀和真后缀有 c 和 coc，最长的长度为 3

$\pi[5]=4$，因为 cococo 相等的真前缀和真后缀有 co 和 coco，最长的长度为 4

$\pi[6]=0$，因为 cococol 没有相等的真前缀和真后缀

$\pi[7]=0$，因为 cococola 没有相等的真前缀和真后缀

即字符串 cococola 的前缀函数为 $[0,0,1,2,3,4,0,0]$。

同理可以计算字符串:

abcabcd 的前缀函数为 $[0,0,0,1,2,3,0]$。

aabaaab 的前缀函数为 $[0,1,0,1,2,2,3]$。

3.2.5 计算前缀函数的朴素算法

一个直接按照定义计算前缀函数的算法：

• 在一个循环中以 $i=1\to n-1$ 的顺序计算前缀函数 $\pi[i]$ 的值。

• 令变量 $j$ 从最大的真前缀长度 $i$ 开始尝试。

• 如果当前长度下真前缀和真后缀相等，则此时长度为 $\pi[i]$，否则令 $j$ 自减 1，继续匹配，直到 $j=0$。

• 如果 $j=0$ 并且没有任何一次匹配，则令 $\pi[i]=0$ 并移至 $i+1$。

代码实现如下：

vector<int> prefix_function(string s){
    int n=(int)s.length();
    vector<int> pi(n);
    for(int i=1;i<n;i++)
        for(int j=i;j>=0;j--)
            if(s.substr(0,j)==s.substr(i-j+1,j)){
                pi[i]=j;
                break;
            }
    return pi;
}

该算法的时间复杂度为 $O(n^3)$，具有很大的优化空间。

3.2.6 计算前缀函数的高效算法

第一个优化

我们观察到相邻的前缀函数值至多增加 1。

因此只需如此考虑：当取一个尽可能大的 $\pi[i+1]$ 时，必然要求新增的 $s[i+1]$ 也与之对应的字符匹配，即 $s[i+1]=s[\pi[i]]$，此时 $\pi[i+1]=\pi[i]+1$。

$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]=3} ~ s_3}_{\pi[i+1]=4} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_i}^{\pi[i]=3} ~ s_{i+1}}_{\pi[i+1]=4}$$

所以当移动到下一个下标时，前缀函数值要么增加 1，要么不变，要么减少。

代码实现如下：

vector<int> prefix_function(string s){
    int n=(int)s.length();
    vector<int> pi(n);
    for(int i=1;i<n;i++)
        for(int j=pi[i-1]+1;j>=0;j--)
            if(s.substr(0,j)==s.substr(i-j+1,j)){
                pi[i]=j;
                break;
            }
    return pi;
}

在经过第一次优化的算法中，计算每个 $\pi[i]$ 时，最优情况是第一次字符串比较就完成了匹配，也就是基础的字符串比较次数是 n-1 次。

而由于存在 j=pi[i-1]+1 (pi[0]=0) 对于最大字符串比较次数的限制，可以看出每次只有在最优情况才会为字符串比较次数的上限累积 1，而每次超过一次的字符串比较消耗的是之后次数的增长空间。

由此我们可以得出字符串比较次数最多的一种情况：至少 1 次字符串比较次数的消耗和最多 $n-2$ 次比较次数的积累，此时字符串比较次数为 n-1 + n-2 = 2n-3。

可见经过第一次优化，计算前缀函数只需要进行 $O(n)$ 次字符串比较，总复杂度降为了 $O(n^2)$。

第二个优化

在第一个优化中，我们讨论了计算 $\pi[i+1]$ 时的最优情况：$s[i+1]=s[\pi[i]]$，此时 $\pi[i+1]=\pi[i]+1$。现在我们更进一步，讨论当 $s[i+1] \neq s[\pi[i]]$ 时如何跳转。

失配时，我们希望找到对于子串 $s[0 \cdots i]$，仅次于 $\pi[i]$ 的第二长度 $j$，使得在位置 $i$ 的前缀性质任得以保持，即 $s[0 \cdots j-1]=s[i-j+1 \cdots i]$。

$$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

如果我们找到了这样的长度 $j$，那么仅需要再次比较 $s[i+1]$ 和 $s[j]$。如果它们相等，那么就有 $\pi[i+1]=j+1$。否则，我们需要找到子串 $s[0 \cdots i]$ 仅次于 $j$ 的第二长度 $j^{(2)}$，使得前缀性质得以保持，如此反复直到 $j=0$。如果 $s[i+1] \neq s[0]$，则 $\pi[i+1]=0$。

因为 $s[0 \cdots \pi[i]-1]=s[i-\pi[i]+1 \cdots i]$，所以对于 $s[0 \cdots i]$ 的第二长度 $j$，有这样的性质：

$$s[0 \cdots j-1]=s[i-j+1 \cdots i]=s[\pi[i]-j] \cdots \pi[i]-1$$

也就是说 $j$ 等价于子串 $s[\pi[i]-1]$ 的前缀函数值，即 $j=\pi[\pi[i]-1]$。同理，次于 $j$ 的第二长度等价于 $s[j-1]$ 的前缀函数值，$j^{(2)}=\pi[j-1]$

显然我们可以得到一个关于 $j$ 的状态转移方程：$j^{(n)}=\pi[j^{(n-1)}-1]，(j^{(n-1)}>0)$

代码实现如下：

vector<int> prefix_function(string s){
    int n=(int)s.length();
    vector<int> pi(n);
    for(int i=1;i<n;i++){
        int j=pi[i-1];
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
    return pi;
}

经过第二次改进的算法不需要进行任何字符串比较，且将时间复杂度优化到了 $O(n)$。

3.2.7 KMP 算法的理论实现

给定一个长度为 $n$ 的文本串 $s$ 和一个长度为 $m$ 的模式串 $p$。

我们构造一个字符串 $p+\#+s$，其中 $\#$ 作为一个既不出现在 $p$ 中也不出现在 $s$ 中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始 $m+1$ 个值（即属于字符串 $p$ 和分隔符的函数值）后其余函数值的意义。根据定义，$\pi[i]$ 为右端点在 $i$ 且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与 $p$ 的前缀相同且右端点位于 $i$ 的最长子串的长度。由于分隔符的存在，该长度不可能超过 $m$。而如果等式 $\pi[i]=m$ 成立，则意味着 $p$ 完整出现在该位置（即其右端点位于位置 $i$）。注意该位置的下标是对字符串 $p+\#+s$ 而言的。

因此如果在某一位置 $i$ 有 $\pi[i]=m$ 成立，则字符串 $p$ 在字符串 $s$ 的 $i-(m-1)-(m+1)=i-2m$ 处出现。

正如在前缀函数的计算中提到的那样，如果我们知道前缀函数的值永远不超过一特定值，那么我们不需要存储整个字符串以及整个前缀函数，而只需要二者开头的一部分。在我们这种情况下意味着只需要存储字符串 $p+\#$ 以及相应的前缀函数值即可。我们可以一次读入字符串 $s$ 的一个字符并计算当前位置的前缀函数值。

因此 KMP 算法仅使用 $O(n+m)$ 的时间以及 $O(n)$ 的空间就能解决单模式匹配问题。

3.2.8 KMP 算法的代码实现

pair<vector<int>,vector<int>> kmp(string s,string p){
    int n=(int)s.size(),m=(int)p.size();
    vector<int> f(n+1),nxt(m+1);
    s="#"+s,p="#"+p;
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[j+1]!=p[i])j=nxt[j];
        if(p[j+1]==p[i])j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while((j==m)||(j&&p[j+1]!=s[i]))j=nxt[j];
        if(p[j+1]==s[i])j++;
        f[i]=j;
    }
    return {f,nxt};
}

3.3 AC 自动机

3.3.1 什么是 AC 自动机

AC 自动机是一种有限状态自动机，它是以 Trie 的结构为基础，结合 KMP 的思想建立的。

3.3.2 AC 自动机的作用

AC 自动机能够高效地进行多模式匹配，即在一个文本串中匹配多个模式串。

3.3.3 AC 自动机的理论实现

AC 自动机的运行原理：构建字典图实现自动跳转，构建失配指针实现多模式匹配。

简单来说，建立一个 AC 自动机需要两步：

1. Trie 结构：将所有模式串构建成一颗 Trie 树
2. KMP 思想：对 Trie 树上所有的结点构造失配指针

3.3.3.1 构建 Trie 树

Trie 树的构建和 Trie 的 insert 操作一模一样。

Trie 树的结点表示某个模式串的前缀（也称为状态），而 Trie 树的边就是状态的转移。

3.3.3.2 构造失配指针

失配指针即 $fail$ 指针。

3.3.3.2.1 $fail$ 指针的基础思想

构建 $fail$ 指针，可以类比 KMP 中构造 next 指针（即 pi[]）的思想。

利用已经求出 $fail$ 指针的结点推导出当前结点的 $fail$ 指针，一般来说通过 BFS 实现即可：

考虑 Trie 中当前的结点 $u$，$u$ 的父结点是 $p$。

假设深度小于 $u$ 的所有结点的 $fail$ 指针都已经求得，那么 $p$ 的 $fail$ 指针显然已经求得。

我们跳转到 $p$ 的 $fail$ 指针指向的结点 $fail[p]$：

• 如果结点 $fail[p]$ 的子结点 $w$ 存在，则让 $u$ 的 $fail$ 指针指向这个结点 $w$。
• 如果结点 $fail[p]$ 的子结点 $w$ 不存在，那么我们继续寻找 $fail[fail[p]]$ 指针指向的结点，直到 $fail$ 指针指向根节点。

如此就完成了 $fail$ 指针的构建。

3.3.3.2.2 $fail$ 指针与 next 指针的比较

共同点：两者都是在 失配 时用于跳转从而避免大量回朔的指针。

不同点：KMP 要求 最长相同真前缀和真后缀，AC 自动机要求 相同后缀。

• KMP 用于单模式匹配，AC 自动机用于多模式匹配。
• $fail$ 指针指向的结点可能对应着前缀不同的模式串。
• AC 自动机在匹配文本串时，同一位上可能匹配多个模式串。
• 因此 $fail$ 指针会在字典树上的结点来回跳转，next 指针则是在线性结构上跳转。

3.3.4 AC 自动机的代码实现

主要框架：

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10,M=256;

int trie[N][M]; // Trie树
int cntword[N]; // 标记是否为模式串的结尾
int fail[N]; // fail指针
int cnt=0; // Trie树结点的下标
int n;
string s;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s); // 插入模式串
    }
    build(); // 构建fail指针
    cin>>s;
    cout<<query(s); // 匹配函数
    return 0;
}

接下来将依次介绍 insert、build 和 query 函数：

1. insert - 构建 Trie 树

void insert(string s){
    int root=0;
    for(int i=0;s[i];i++){
        int next=s[i];
        if(!trie[root][next]){
            trie[root][next]=++cnt;
        }
        root=trie[root][next];
    }
    cntword[root]++;
}

与 Trie 树的 insert 一模一样，不详细介绍。

1. build - 构建 $fail$ 指针

void build(){
    queue<int> q;
    for(int i=0;i<M;i++){
        if(trie[0][i]){
            fail[trie[0][i]]=0;
            q.push(trie[0][i]);
        }
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<M;i++){
            if(trie[now][i]){
                fail[trie[now][i]]=trie[fail[now]][i];
                q.push(trie[now][i]);
            }else{
                trie[now][i]=trie[fail[now]][i];
            }
        }
    }
}

• 首先声明队列 $q$ 用于 BFS，这里的字典树根节点为 0，我们将根节点的子节点一一入队。
• 然后开始进行 BFS，每次取出队首结点 $now$，求 $now$ 的子节点的 $fail$ 指针。
• 接着遍历字符集：
• 如果字符 $i$ 对应的子结点存在，我们就将该子结点的 $fail$ 指针赋值为 $fail[now]$ 的字符 $i$ 对应的结点。
• 否则将 $fail[now]$ 的字符 $i$ 对应的子结点编号赋值给 $now$。

代码中存在两处与之前的理论分析不一致之处：

• 首先，按照分析，应该使用 while 循环，让 $fail$ 指针不停跳转，判断是否存在对应结点，但此处并非如此。
• 其次，此处直接将 $fail[now]$ 的子结点赋值为 $now$ 的子结点。

这两处地方结合在一起完成了路径压缩，能在 $O(1)$ 的时间内对单个结点进行 $fail$ 指针的构造。

1. query - 匹配函数

int query(string s){
    int now=0,ans=0;
    for(int i=0;s[i];i++){
        now=trie[now][(int)s[i]];
        for(int j=now;j&&cntword[j]!=-1;j=fail[j]){
            ans+=cntword[j];
            cntword[j]=-1;
        }
    }
    return ans;
}

• 声明 $now$ 作为 Trie 上当前匹配到的结点，$ans$ 即返回的答案
• 循环遍历文本串，$now$ 在 Trie 上跟踪当前字符。
• 利用 $fail$ 指针找出所有匹配的模式串，累加到答案中。

这里的 $now$ 并一直在往 Trie 后跳转，而是在图上穿梭跳转。

---

4. 总结与拓展

至此，我们已经学习了三种常用的自动机，但是这三种算法和“自动机”似乎毫无关联，所以接下来，我们需要重新认识自动机。

4.1 自动机的形式化定义

一个确定有限状态自动机（DFA）是由以下五个部分：

1. 字符集 $\sum$，该自动机只能输入这些字符。
2. 状态集合 $Q$。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
3. 起始状态 $s$，$s\in Q$，是一个特殊的状态。
4. 接受状态 $F$，$F\subseteq Q$，是一组特殊的状态。
5. 转移函数 $\delta$，$\delta$ 是一个接受两个参数并返回一个值的函数，其中，第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。

组成的五元组 $(Q,\sum,\delta,s,F)$

DFA 的作用就是识别字符串，一个自动机 $A$，若它能识别（接受）字符串 $S$，那么 $A(S)=True$，否则 $A(S)=False$。

当一个 DFA 读入一个字符串时，从初始状态起按照转移函数一个一个字符地转移。如果读入完一个字符串的所有字符后位于一个接受状态，那么我们称这个 DFA 接受 这个字符串，反之我们称这个 DFA 不接受 这个字符串。

如果一个状态 $v$ 没有字符 $c$ 的转移，那么我们令 $\delta(v,c)=null$，而 $null$ 只能转移到 $null$，且 $null$ 不属于接受状态集合。无法转移到任何一个接受状态的状态都可以视作 $null$，或者说，$null$ 代指所有无法转移到任何一个接受状态的状态。

我们拓展定义转移函数 $\delta$，令其第二个参数可以接收一个字符串：$\delta(v,S)=\delta(\delta(v,S[1],S[2\cdots|S|]))$，拓展后的转移函数就可以表示从一个状态起接收一个字符串后转移到的状态。那么，$A(S)=[\delta(s,S)\in F]$。

此时，我们可以回过头来看看之前学习的三种常用自动机。

4.1.1 Trie

对于 Trie：

• 接受且仅接受指定的字符串集合中的元素。
• 接受状态为每个字符串插入到 Trie 树时到达的状态。
• 转移函数为 Trie 上的边。

4.1.2 KMP 算法

KMP 算法可以视作自动机，基于字符串 $s$ 的 KMP 自动机：

• 接受且仅接受以 $s$ 为后缀的字符串。
• 接受状态为 $|s|$。
• 转移函数为：

$$\delta(i,c)=\begin{cases}i+1&s[i+1]=c\\ 0&s[1]\ne c\land i=0\\ \delta(\pi(i),c)&s[i+1]\ne c\land i>0 \end{cases}$$

4.1.3 AC 自动机

对于 AC 自动机：

• 接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串，也就是 Trie+KMP。

4.2 拓展 1：常用自动机的深入

4.2.1 Trie

• 检索字符串 $\surd$
• AC 自动机 $\surd$
• 维护异或极值
• 维护异或和
• 01-trie 合并
• 插入&删除
• 全局加一
• 可持久化字典树

4.2.2 KMP 算法

• 在字符串中查找子串
• AC 自动机
• 统计每个前缀的出现次数
• 一个字符串中本质不同的子串数量
• 字符串压缩

4.3 拓展 2：其他自动机

• Trie(字典树)
• KMP 算法
• AC 自动机
• 后缀自动机：接受且仅接受指定字符串的后缀
• 广义后缀自动机：接受且仅接受指定的字符串集合中的某个元素的后缀，即 Trie+SAM
• 回文自动机：接受且仅接受某个字符串的所有回文子串的中心及右半部分
• 序列自动机：接受且仅接受指定字符串的子序列

---

全文结束，谢谢阅读！

---

最后更新: 2022-12-31 06:35:42

评论