第 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 的搜索实现内容代码javapublic 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内容为模式的每个字符分配一个状态加上接受状态共 M1 个状态。表格结构dfa[c][j]行为字母表字符c列为状态j。物理含义构建过程就是填满这个二维数组。第 30 页匹配转移内容“Match transition. If in state j and next char c pat.charAt(j), go to j1.”图示如果当前状态是j且读入的字符刚好等于模式中第j个字符那么状态前进到j1。物理含义填表动作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个字符。如果第j1个字符不匹配我们需要根据模式自身的结构寻找次长的匹配前缀。这相当于把模式的前缀作为文本重新走一遍 DFA。第 32 页利用状态 X 实现 O(1) 构建内容为了不每次都从头模拟维护一个状态X。X表示“除了当前状态j之外最长的能够匹配当前文本后缀的模式前缀”。X的初始值为 0。更新X的物理动作X dfa[pat.charAt(j)][X]。物理含义在构建状态j1的转移表时如果遇到不匹配字符c它的去向其实与在状态X下遇到字符c的去向完全相同。因此对于状态j的所有不匹配转移直接复制状态X的那一行dfa[c][j] dfa[c][X]。这只需要 O(1) 的时间。第 35 页DFA 构建的 Java 实现内容javapublic 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个字符时转移后的状态是j1。2. 左值写内存与右值读内存的物理隔离左值dfa[...][j] ...这是在构建Build二维数组将状态转移结果写入内存中的j这一列。右值X dfa[...][X]这是在读取Run二维数组取出已经构建好的状态X在遇到特定字符时的去向。这两行代码看着形式相似如果不刻意区分可能弄混3. 状态X的物理本质最长真前后缀LPSX是一个唯一的整数它维护的是模式自身的最长真前后缀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 jdfa[c][X]这一格早已被算好直接查表借用省去了 O(j) 的重新模拟。这个数学证明正是缺失的一环或许往里看会很复杂但我们可以把它当结论用这样会舒服很多。5. 覆盖正确匹配的转移第二行代码dfa[pat.charAt(j)][j] j 1;物理动作无论前面复制了什么如果在状态j遇到了正确的字符pat.charAt(j)状态必须向前推进变成j1。这说明正确情况的更新不受影响。6. 影子X的自我更新第三行代码X dfa[pat.charAt(j)][X];物理动作将当前正确的字符pat.charAt(j)喂给上一轮的X状态查表得到下一轮的最长真前后缀长度。单一性这里没有并行可能性强制输入了正确的字符确保X始终沿着模式自身的正确路径演进。7. 历史信息的坍缩状态合并在 DFA 中无论文本历史是AC、BC还是CC只要它们触发了相同的失败并清零或者退化到了相同的后缀DFA 就会把它们压缩坍缩到同一个状态。DFA 根本不在乎你前面经历了多少复杂的、多维的历史错误。它只在乎“当前文本后缀能匹配模式前缀的长度”。只要后缀相同未来的状态转移就完全一致。这种等价类划分正是 DFA 能够以有限状态处理无限长文本的根本原因。