第 20 页：KMP 的物理直觉
内容：
假设我们在文本中搜索模式
BAAAAAAA。假设已经匹配了 5 个字符，但在第 6 个字符发生不匹配。此时我们知道文本中刚读过的 6 个字符是
BAAABA。传统的暴力算法（图上半部分红字）会回退文本指针
i，去尝试各种对齐。KMP 算法（图下半部分）说明，不需要回退文本指针，
i直接继续往后读。物理含义：
当发生不匹配时，文本指针
i已经走过了一段路程（比如匹配了前 5 个字符）。这段路程的字符内容是已知的。KMP 利用了这个已知信息，它通过分析模式本身的结构，推断出“即使不回退文本指针，模式应该滑动到哪里继续比较”。
核心目标：文本指针
i永不回退（no backup）。第 21 页：DFA（确定有限状态自动机）
内容：
DFA 是一种抽象的字符串搜索机器。包含有限个状态（0 到 M），每个字符有且只有一条出边。
内部表示：一个二维数组
dfa[c][j]。c是字符，j是当前状态。含义是：如果当前在状态j，读入字符c，下一个状态是什么。图中展示了模式
A B A B A C的 DFA 表格和状态转移图。状态 6 是停止（halt/accept）状态。物理含义：
DFA 的物理载体就是一个二维整数数组
dfa[char][state]。在 Java 中，dfa[c][j]占用的内存是一个整数。状态
j代表“当前已经成功匹配了模式的前j个字符”。状态转移图是一张有向图，每个节点（状态）对字母表中的每个字符都有一条有向边。
第 22-23 页：DFA 模拟演示
内容：
给定文本
A A B A C A A B A B A C A A，以及模式ABABAC的 DFA。第 22 页展示了文本读入时的状态跳转。初始状态 0，读入 A 进入 1，读入 A 留在 1... 最终读入 C，进入状态 6。
第 23 页高亮了进入状态 6 的过程，标注“substring found”。
物理含义：
模拟动作只有一行：
j = dfa[txt.charAt(i)][j]。每次读取一个文本字符，将其作为
dfa数组的第一维索引，将当前状态j作为第二维索引，取出下一个状态并赋给j。这个动作只涉及数组寻址，没有任何字符比较。
第 24 页：DFA 状态的物理含义
内容：
问题：读入文本的某个位置后，DFA 的状态代表什么？
答案：状态 = 当前文本后缀中，能够匹配模式最长前缀的长度。
例子：文本是
B C B A A B A C A，读入索引0..6（即B C B A A B A）。模式是A B A B A C。此时文本后缀
A B A与模式前缀A B A匹配，所以状态停在 3。物理含义：
状态
j本质上记录的是文本当前后缀和模式前缀的重合度。当发生不匹配时，我们不需要回退文本指针，因为状态
j已经隐含了回退后重新匹配所需的所有信息。第 25-26 页：KMP 的搜索实现
内容：
代码：
java
public int search(String txt) { int i, j, N = txt.length(); for (i = 0, j = 0; i < N && j < M; i++) j = dfa[txt.charAt(i)][j]; if (j == M) return i - M; else return N; }
第 26 页展示可以用于输入流（
In in）的版本。关键特性：
i一直在自增，没有i -= j这种回退操作（no backup）。时间复杂度：模拟 DFA 最多 N 次字符访问。
物理含义：
i是只读单向游标，随着文本流前进。
j通过查表直接跳跃。彻底消灭了第 16 页的i -= j。现在问题转化为：如何构建这个
dfa[][]数组？第 27-29 页：构建 DFA
内容：
为模式的每个字符分配一个状态（加上接受状态，共 M+1 个状态）。
表格结构：
dfa[c][j]，行为字母表字符c，列为状态j。物理含义：
构建过程就是填满这个二维数组。
第 30 页：匹配转移
内容：
“Match transition. If in state j and next char c == pat.charAt(j), go to j+1.”
图示：如果当前状态是
j，且读入的字符刚好等于模式中第j个字符，那么状态前进到j+1。物理含义：
填表动作：
dfa[pat.charAt(j)][j] = j + 1。这是 DFA 图中向右指的黑色箭头。
第 31 页：不匹配转移（难点）
内容：
“Mismatch transition. If in state j and next char c != pat.charAt(j), then the last j-1 characters of input are pat[1..j-1], followed by c.”
为了计算不匹配时的去向，需要模拟
pat[1..j-1]后接字符c。如果每次都去模拟，需要 O(j) 步。
物理含义：
因为之前匹配了
j个字符，文本当前的结尾其实是模式的前j个字符。如果第j+1个字符不匹配，我们需要根据模式自身的结构，寻找次长的匹配前缀。这相当于把模式的前缀作为文本，重新走一遍 DFA。
第 32 页：利用状态 X 实现 O(1) 构建
内容：
为了不每次都从头模拟，维护一个状态
X。
X表示“除了当前状态j之外，最长的能够匹配当前文本后缀的模式前缀”。
X的初始值为 0。更新
X的物理动作：X = dfa[pat.charAt(j)][X]。物理含义：
在构建状态
j+1的转移表时，如果遇到不匹配字符c，它的去向其实与在状态X下遇到字符c的去向完全相同。因此，对于状态
j的所有不匹配转移，直接复制状态X的那一行：dfa[c][j] = dfa[c][X]。这只需要 O(1) 的时间。
第 35 页：DFA 构建的 Java 实现
内容：
java
public KMP(String pat) { this.pat = pat; M = pat.length(); dfa = new int[R][M]; dfa[pat.charAt(0)][0] = 1; for (int X = 0, j = 1; j < M; j++) { for (int c = 0; c < R; c++) dfa[c][j] = dfa[c][X]; // Copy mismatch cases. dfa[pat.charAt(j)][j] = j + 1; // Set match case. X = dfa[pat.charAt(j)][X]; // Update restart state. } }物理含义（逐行动作）：
dfa[pat.charAt(0)][0] = 1;：初始化状态 0，如果读入模式的第一个字符，必定进入状态 1。
for (int c = 0; c < R; c++) dfa[c][j] = dfa[c][X];：先将状态X的所有转移复制给状态j。这处理了所有不匹配的情况。
dfa[pat.charAt(j)][j] = j + 1;：覆盖匹配的情况，前进到下一个状态。
X = dfa[pat.charAt(j)][X];：更新X。将当前字符pat.charAt(j)送入状态X，计算新的重启状态。复杂度：外层循环 M 次，内层循环 R 次，时间 O(MR)，空间 O(MR)。
第 36 页：性能分析
内容：
搜索：最多访问 N 个字符。
构建 DFA：时间和空间正比于 R*M。
物理含义：
KMP 提供了严格的线性时间保证。无论文本和模式有多重复，它都不会退化到 O(MN)。
一、dfa的构建
1. 基础定义与指针错位
在构建
dfa[c][j]时，必须区分j的三重物理身份：
索引：
pat.charAt(j)代表模式串的第j个字符（范围 0 到 5，是从0开始数的）。状态：
j作为状态值时，代表当前已经成功匹配了模式的前j个字符（范围 0 到 6）。错位：因为索引从 0 开始，状态从 0 开始，但每成功匹配一个字符状态加 1。所以处理第
j个字符时，转移后的状态是j+1。2. 左值（写内存）与右值（读内存）的物理隔离
左值（
dfa[...][j] = ...）：这是在构建（Build）二维数组，将状态转移结果写入内存中的j这一列。右值（
X = dfa[...][X]）：这是在读取（Run）二维数组，取出已经构建好的状态X在遇到特定字符时的去向。这两行代码看着形式相似，如果不刻意区分可能弄混
3. 状态
X的物理本质：最长真前后缀（LPS）
X是一个唯一的整数，它维护的是模式自身的最长真前后缀（Longest Proper Prefix-Suffix）的长度。
在构建主状态
j（正确输入的前缀）时，X相当于维护了一个去除了首字符的“影子输入”（后缀组）。
X在物理上是一个一维的标量，但在查表时，它作为数组的第二个下标，指向了二维数组中的整整一列。X中所字符串相当于被维护在一个队列内，队列的动作是，首轮首字符去除，后续字符入队进行匹配；一旦匹配出错，全部出队。
4. 为什么可以“借用”状态
X？（状态等价性）第一行代码：
dfa[c][j] = dfa[c][X];
物理动作：在状态
j遇到不匹配字符c时，直接复制状态X遇到c的去向。原因：当在状态
j（匹配了pat[0..j-1]）遇到错误字符c时，我们要找当前文本后缀能匹配模式前缀的最长长度。因为X已经是pat[0..j-1]的最长真后缀，所以此时文本的后缀等价于模式的前缀X。结论：状态
j遇到c的失败，在数学等价性上，完全等同于状态X遇到c的失败。由于X < j，dfa[c][X]这一格早已被算好，直接查表借用，省去了 O(j) 的重新模拟。这个数学证明正是缺失的一环，或许往里看会很复杂，但我们可以把它当结论用，这样会舒服很多。
5. 覆盖正确匹配的转移
第二行代码：
dfa[pat.charAt(j)][j] = j + 1;
物理动作：无论前面复制了什么，如果在状态
j遇到了正确的字符pat.charAt(j)，状态必须向前推进，变成j+1。这说明正确情况的更新不受影响。6. 影子
X的自我更新第三行代码：
X = dfa[pat.charAt(j)][X];
物理动作：将当前正确的字符
pat.charAt(j)喂给上一轮的X状态，查表得到下一轮的最长真前后缀长度。单一性：这里没有并行可能性，强制输入了正确的字符，确保
X始终沿着模式自身的正确路径演进。7. 历史信息的坍缩（状态合并）
在 DFA 中，无论文本历史是
AC、BC还是CC，只要它们触发了相同的失败并清零，或者退化到了相同的后缀，DFA 就会把它们压缩（坍缩）到同一个状态。
DFA 根本不在乎你前面经历了多少复杂的、多维的历史错误。
它只在乎“当前文本后缀能匹配模式前缀的长度”。只要后缀相同，未来的状态转移就完全一致。这种等价类划分，正是 DFA 能够以有限状态处理无限长文本的根本原因。