目录

 

前言

朴素子字符串查找算法

KMP 算法的基本思想

基于 DFA 的 KMP 实现

 

原文链接

 

朴素子字符串查找算法

KMP 算法是用来解决 子字符串查找 问题的算法，这个问题有一个很朴素（暴力）的解决方式，通常的写法是：

 

 

def bf_search(txt: str, pat: str) -> int: i, j, txt_len, pat_len = 0, 0, len(txt), len(pat) while i < txt_len and j < pat_len: if txt[i] == pat[j]: j += 1 else: i -= j # 回退文本指针 i j = 0 # 回退模式指针 j i += 1 if j == pat_len: return i - pat_len return -1

当pat[j] 与 txt[i] 匹配失败后，i 会 显式的回退， 然后在  i+=1 的位置重新开始匹配

KMP 算法的基本思想

 

在模式指针在 j 处出现了不匹配的情况，那么，这个时候，文本字符串必然已经匹配了 pat[0:j] 这部分模式字符串，此时，在朴素算法中， 我们会回退文本指针并在 右移一位 后继续尝试匹配模式字符串。

也就是说，接下来要尝试匹配的文本字符串是以 pat[1:j] 这个前缀开头的字符串，我们可以利用这一特性，避免重新匹配这个前缀。

这样一来，所有已经匹配过的文本字符都不需要重新匹配，只需要不断调整模式字符串完成匹配就可以了。

x状态的理解

这里的x状态我们应该重两个方向来看

1. 重朴素算法的角度，当i匹配失败时，那么下一个要匹配的是，i 先回退 再加1的位置，那么当前要匹配txt是BABAD

2.从自动机状态转换图来看，若新的输入是 BABA,那么我们就可以到达一个状态，而且这个状态是可以输入D的。

从字符匹配的角度来看，新的txt是 BABAD, 而pat 是ABABAC, 第一个就不相同，就不应该继续向后匹配。但是我们重新输入BABA不是为了去匹配字符ABAB, 而是， 为了让自动机进入状态x， 从自动机角度，输入BABA是合法的，他会按照自动机的角度进去某一个状态，而且可以肯定的是，该状态一定  是 允许 输入 D的， 而我们的目的就是为了不回退，输入D。

我们把这个状态叫做【重启状态】，在状态 j 处匹配成功时，下一个状态为 j + 1，匹配失败时，重新匹配会在状态 j - 1 处到达重启状态，此时， 在状态 j 处的状态转换应该和 重启状态 处的状态转换相同。

基于 DFA 的 KMP 实现

这个状态机的状态就是模式指针，可能值为 [0, len(pat)], 状态为 len(pat) 时，说明成功完成模式字符串的匹配这个状态机 构建时 的输入是模式字符串中的字符，对于每一个状态来说，输入某一个字符后会转换为 下一个状态这个状态机 运行时 的输入是文本字符串中的字符，我们根据输入的文本字符、当前状态和状态机来转换状态

比如，基于模式字符串 ABABAC 构建得到的状态机是这样的：

解释：

在状态为 0 且输入的字符是 A 时，说明匹配字符 pat[0] 成功，下一个需要匹配的字符为 pat[1], 因此下一个状态为 1在状态为 0 且输入的字符不是 A 时，说明匹配字符 pat[0] 失败，需要移动文本字符并重新从状态 0 开始匹配，因此下一个状态为 0

可以通过 [输入][状态] = 下一个状态 或 [状态][输入] = 下一个状态 的形式来表示这个状态机，当状态对应的 模式字符 和输入对应的 文本字符 相同时， 说明匹配成功，下一个状态必然为 当前状态 + 1, 也就是说，我们需要考虑的是不同时应该怎么解决。

在朴素算法中，在位置 j 出现不匹配时，我们会回退文本指针并右移 1 位重新开始匹配，这时，这部分 文本字符串 字串等于 pat[1:j] 这个 模式字符串 子串：

txt: A B A B A D A i pat: A B A B A C 1 j 5

pat[1:j] 对应的是 BABA 这个子串，把这个子串放到 DFA 中重新匹配最后可以达到的状态为 3，也就是说，在匹配过程中，就算匹配失败，重新匹配时， 也必然会在继续匹配到 j - 1 时到达另一个状态。

我们把这个状态叫做【重启状态】，在状态 j 处匹配成功时，下一个状态为 j + 1，匹配失败时，重新匹配会在状态 j - 1 处到达重启状态，此时， 在状态 j 处的状态转换应该和 重启状态 处的状态转换相同。

假设状态 j 的重启状态为 X，那么状态 j 处可能的转换就应该是：

for ch in pat_chrs: # 遍历模式字符串中的字符 dfa[ch][j] = dfa[ch][x] # 不匹配时转换和重启状态 x 处相同 dfa[pat[j]][j] = j + 1 # 匹配时下一个状态为 j + 1

同时，状态 j 和状态 j + 1 的重启状态是存在递推关系的，假如状态 j 的重启状态为 X，那么，我们将我们将 j 处的字符作为重启状态的输入， 得到的下一个值不就应该是 j + 1 的重启状态了吗？

x = dfa[pat[j]][x] # state x, in pat[j]

我们可以轻易得到状态为 0 时的状态转换和重启状态（你第一个字符都不匹配，重启状态肯定是 0 啊），然后根据状态的转换规律就可以很容易的构建 DFA 了：

x, dfa[pat[0]][0] = 0, 1 for j in range(1, pat_len): for ch in pat_chrs: dfa[ch][j] = dfa[ch][x] dfa[pat[j]][j] = j + 1 // pat[j]会覆盖上一行的赋值 x = dfa[pat[j]][x] // 在状态x 输入 pat[j] 就是 j + 1 时的重启状态

使用 DFA 来查找子字符串的过程就很简单了，就是跑这个状态机的过程：

while i < txt_len and j < pat_len: j = dfa[txt[i]][j] # state => j, in => txt[i], next state => dfa[txt[i]][j] i += 1 if j == pat_len: return i - pat_len return -1

注意 ： txt 永远不会重复输入一个字符。 i 匹配失败，下一个输入应该是 i+1.