字符串匹配算法之 KMP：原理与实现

字符串匹配是计算机科学中一个 fundamental 的问题，其目的是在一个较长的文本串（Text）中查找一个较短的模式串（Pattern）出现的位置。暴力匹配算法虽然简单易懂，但其时间复杂度在最坏情况下可以达到 O(m*n)，其中 n 为文本串长度，m 为模式串长度。为了提高效率，Knuth-Morris-Pratt 算法（简称 KMP 算法）应运而生，它通过利用模式串自身的信息来避免不必要的回溯，将时间复杂度优化至 O(n+m)。

一、KMP 算法的核心思想：利用已匹配信息，避免重复比较

KMP 算法的核心在于利用已经匹配过的字符信息，避免在文本串和模式串不匹配时，模式串指针无谓地回退到起始位置。具体来说，当模式串与文本串在某个位置不匹配时，KMP 算法不会像暴力匹配那样将模式串指针简单地回退到起始位置，而是根据模式串自身的特点，将模式串指针回退到一个“安全”的位置，继续进行匹配。

二、Next 数组：模式串的“自我认知”

为了实现上述思想，KMP 算法引入了 Next 数组 的概念。Next 数组的长度与模式串相同，每个元素 next[i] 表示：当模式串的第 i 个字符与文本串不匹配时，模式串指针应该回退到的位置。

更准确地说，next[i] 表示模式串中以 i-1 结尾的后缀与模式串的前缀能够匹配的最大长度（且该长度小于 i）。举例说明：

假设模式串为 "ABABCABAB"，其 Next 数组为：[-1, 0, 0, 1, 2, 0, 1, 2, 3]。

• next[0] = -1：表示当模式串的第一个字符与文本串不匹配时，模式串指针需要向右移动一位。
• next[4] = 2：表示当模式串的第五个字符 'C' 与文本串不匹配时，需要将模式串指针回退到索引为 2 的位置（即字符 'A'），因为 "ABABC" 中以 'B' 结尾的后缀 "AB" 与模式串的前缀 "AB" 相同，且长度为 2。
• next[8] = 3：表示当模式串的第九个字符 'B' 与文本串不匹配时，需要将模式串指针回退到索引为 3 的位置（即字符 'B'），因为 "ABABCABAB" 中以 'A' 结尾的后缀 "ABA" 与模式串的前缀 "ABA" 相同，且长度为 3。

三、Next 数组的构建：递推求解

Next 数组的构建是 KMP 算法的关键步骤。我们可以通过递推的方式来求解 Next 数组：

1. 初始化：next[0] = -1
2. 假设已知 next[0] 到 next[i-1]，求解 next[i]：
3. 令 k = next[i-1]，比较 pattern[i-1] 和 pattern[k]：
   • 如果 pattern[i-1] == pattern[k]，则 next[i] = k + 1。
   • 如果 pattern[i-1] != pattern[k]，则令 k = next[k]，重复上述比较过程，直到 k == -1 或者 pattern[i-1] == pattern[k]。
   • 如果 k == -1，则 next[i] = 0。

四、KMP 算法的实现：基于 Next 数组的匹配

有了 Next 数组，KMP 算法的匹配过程就变得非常高效：

1. 初始化：i = 0（文本串指针），j = 0（模式串指针）
2. 循环比较 text[i] 和 pattern[j]：
3. 如果 text[i] == pattern[j]，则 i++，j++
4. 如果 text[i] != pattern[j] 且 j != -1，则令 j = next[j]（利用 Next 数组回退模式串指针）
5. 如果 text[i] != pattern[j] 且 j == -1，则 i++（模式串第一个字符就不匹配，文本串指针向右移动一位）
6. 如果 j == m（模式串长度），则表示找到一个匹配，返回匹配位置 i - j，并令 j = next[j] 继续查找下一个匹配。
7. 如果 i == n（文本串长度），且 j < m，则表示匹配失败。

五、KMP 算法的代码实现 (Python)

```python
def compute_next(pattern):
"""计算模式串的 Next 数组"""
n = len(pattern)
next_array = [-1] * n
k = -1
for i in range(1, n):
while k > -1 and pattern[i - 1] != pattern[k]:
k = next_array[k]
if pattern[i - 1] == pattern[k]:
k += 1
next_array[i] = k
return next_array

def kmp_search(text, pattern):
"""KMP 字符串匹配算法"""
n = len(text)
m = len(pattern)
next_array = compute_next(pattern)
i = 0
j = 0
matches = []
while i < n:
if j == -1 or text[i] == pattern[j]:
i += 1
j += 1
else:
j = next_array[j]
if j == m:
matches.append(i - j)
j = next_array[j]
return matches

示例

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
next_array = compute_next(pattern)
print(f"Next 数组: {next_array}")
matches = kmp_search(text, pattern)
print(f"匹配位置: {matches}")
```

六、总结

KMP 算法通过预先计算模式串的 Next 数组，巧妙地利用了已匹配信息，避免了不必要的回溯，从而将字符串匹配的时间复杂度优化至 O(n+m)。这使得 KMP 算法在处理大规模字符串匹配问题时具有显著的优势，被广泛应用于文本编辑器、搜索引擎等领域。理解 KMP 算法的原理和实现，对于深入学习算法和提高编程能力具有重要意义。