有限自动机（Finite Automaton）

有限自动机可以看成一种特殊的有向图：顶点是状态，边上标着输入符号；机器始终处在某一个状态，读入一个符号就沿对应边跳到下一状态。它和一般的图相比，多了「按输入驱动转移」的执行语义，因此特别适合做模式识别和字符串扫描。

编译器词法分析里大量使用自动机；更偏形式语言的讨论见自动机理论。本章站在数据结构视角：弄清自动机是什么，以及如何用它快速匹配字符串。

试一试状态转移图与转移表：

基本构成

一台（确定）有限自动机通常记为五元组 $(Q, \Sigma, \delta, q_0, F)$ ：

符号	含义
$Q$	有限的状态集合
$\Sigma$	字母表（可出现的输入字符集合）
$\delta: Q \times \Sigma \to Q$	转移函数：当前状态 + 读入字符 → 下一状态
$q_0 \in Q$	初始状态
$F \subseteq Q$	接受状态（终结态）集合

确定性（DFA）：每个状态对每个字符至多（通常恰好）有一条出边，下一步唯一。
非确定性（NFA）：同一状态读同一字符可能有多个去向，还可能有 $\varepsilon$ 转移。NFA 与 DFA 识别能力等价，但 DFA 跑起来更干脆——读一个字符走一步，无需回溯或维护状态集合。

匹配一段输入 $w = c_1 c_2 \ldots c_n$ 时，从 $q_0$ 出发依次转移：

q_{i} = \delta(q_{i-1}, c_i)

若最终（或中途，取决于用法）落在 $F$ 中的某个状态，则称自动机接受该串（或在该位置报告一次匹配）。整段扫描只做 $n$ 次转移，时间 $O(n)$ ，与模式有多复杂无关——复杂都摊在预处理构造 $\delta$ 上。

用自动机做字符串匹配

朴素匹配：模式 $P$ 长度 $m$ ，文本 $T$ 长度 $n$ ，每个对齐位置比较，最坏 $O(nm)$ 。
自动机方法：先把「已经匹配了模式的多长前缀」编码成状态，再对 $T$ 只扫一遍，总时间 $O(n + \text{预处理})$ 。

状态含义

对模式 $P = p_0 p_1 \ldots p_{m-1}$ （下标从 0），构造一台匹配自动机，状态取

Q = \{0, 1, 2, \ldots, m\}

其中状态 $k$ 表示：当前已匹配上 $P$ 的长度为 $k$ 的前缀（即刚读过的一段后缀等于 $P[0..k)$ ）。特别地：

状态 $0$ ：什么都还没匹配上；
状态 $m$ ：整个模式已匹配成功，是接受状态（可设 $F = \{m\}$ ；若要找所有出现位置，到达 $m$ 时报告一次，再按转移继续扫）。

转移函数在算什么

读入字符 $c$ 时，若当前在状态 $k$ ，理想情况是： $c = p_k$ ，则转到 $k+1$ 。
若对不上，不能简单退回 $0$ ——文本里可能已经拼出了模式的某个真前缀。正确做法是：

看「当前已匹配的前缀 $P[0..k)$ 再接上 $c$ 」得到的串，它的最长后缀若同时也是 $P$ 的前缀，长度是多少，就转到那个长度对应的状态。

形式化：设 $\sigma(k, c)$ 表示串 $P[0..k) + c$ 的所有后缀里，同时也是 $P$ 前缀的最大长度，则

\delta(k, c) = \sigma(k, c)

对接受状态 $m$ 也一样：匹配成功后再读字符，相当于从「已匹配完整个 $P$ 」继续找下一个可能的重叠出现。

例子： $P = \texttt{abab}$

状态 $0..4$ 。字母表里我们关心 a、b（其它字符都回到合适的前缀长度，往往是 0）。

状态 $k$	含义（已匹配前缀）	读 `a`	读 `b`
0	$\varepsilon$	1（对齐到 `a`）	0
1	`a`	1（仍是前缀 `a`）	2（`ab`）
2	`ab`	3（`aba`）	0
3	`aba`	1	4（`abab`，接受）
4	`abab`	3（后缀 `ab`+`a` → `aba`）	0

在文本 aababab 上跑：

文本:  a a b a b a b
状态: 0→1→1→2→3→4→3→4
                    ↑     ↑
                 报告匹配  再次匹配

第二次到达状态 4 时，利用了模式的自重叠（abab 的后缀 ab 又是前缀），无需把窗口整段拖回去重比。

如何构造转移表

暴力：对每个状态 $k$ 、每个字符 $c$ ，显式取出串 $P[0..k)+c$ ，再试最长前缀长度，预处理约 $O(m^2|\Sigma|)$ ，对短模式够用。

更常见的是借助失配函数（与 KMP 的 next / prefix 函数同一思想）加速构造，使预处理降到大约 $O(m|\Sigma|)$ ：

先算数组 $\pi[1..m)$ ： $\pi[q]$ = 「 $P[0..q)$ 的真后缀中，同时也是 $P$ 前缀」的最长长度。
（ $\pi[0]$ 无定义或不用；计算方式与 KMP 相同：前后指针滑动。）
对 $k = 0..m$ $k = 0.. m$ 、 $c \in \Sigma$ $c \in Σ$ ：
- 若 $k < m$ 且 $c = p_k$ ，则 $\delta(k,c) = k+1$ ；
- 否则若 $k = 0$ ，则 $\delta(0,c) = 0$ （或仅当 $c=p_0$ 时为 1，上面已覆盖）；
- 否则 $\delta(k,c) = \delta(\pi[k], c)$ ——失配后跳到次长前缀状态，再问这个字符该怎么走（可用递推/缓存避免重复算）。

直觉：失配时「已经读过的那一段」里仍可能藏着更短的合法前缀， $\pi$ 指出该退到哪里，不必从头比。

伪代码（扫描阶段）：

// 预处理得到 δ[0..m][Σ]
q = 0
for i = 0 .. n-1:
    q = δ[q][T[i]]
    if q == m:
        报告：模式在 i-m+1 处出现

扫描严格 $O(n)$ 次转移；每次转移 $O(1)$ （转移表）或 $O(|\Sigma|)$ 量级可忽略。整体 $O(n + m|\Sigma|)$ 量级，远好于朴素的 $O(nm)$ 。

和 KMP、AC 自动机的关系

方法	解决什么	与自动机的关系
匹配自动机（上文）	单模式在文本中的所有出现	显式构造 $\delta$ ，按 DFA 跑文本
KMP	同上	不存完整 $\delta$ ，运行时用 $\pi$ 在失配时跳转，本质是同一台自动机的压缩实现
Aho–Corasick	多模式同时匹配	把多模式做成一棵 Trie，再加失败指针，等价于一台更大的自动机；扫描仍 $O(n + \text{命中次数})$

多模式场景（敏感词过滤、多关键字检索）：先把所有模式插入 Trie，再 BFS 上计算每个结点的失败指针（指向「当前前缀的最长真后缀」对应结点），扫描文本时沿 Trie 走，失配则跳失败指针——这就是常说的 AC 自动机。单模式时它退化成与 KMP / 匹配自动机同类的行为。

小结

有限自动机 = 带输入标签的有向图 + 起止状态；DFA 读入线性扫描，匹配本身是 $O(n)$ 。
字符串快速匹配的关键：用状态记住「模式前缀匹配了多长」，转移时处理失配与自重叠。
预处理建表（或 KMP 的 $\pi$ ），扫描一遍文本即可找出所有出现；多模式用 AC 自动机。
词法分析里「正则 → NFA → DFA」是同一套工具换了构造来源；数据结构这边先掌握「模式 → 匹配自动机 → 线性扫描」即可。

相关阅读：图 · 自动机理论 · 构建自动机

有限自动机（Finite Automaton）

# 有限自动机（Finite Automaton）

# 基本构成

# 用自动机做字符串匹配

# 状态含义

# 转移函数在算什么

# 例子：P=ababP = \texttt{abab}P=abab

# 如何构造转移表

# 和 KMP、AC 自动机的关系

# 小结

有限自动机（Finite Automaton）

基本构成

用自动机做字符串匹配

状态含义

转移函数在算什么

例子： $P = \texttt{abab}$

如何构造转移表

和 KMP、AC 自动机的关系

小结