原理

在日常实践中，我们常常有这样的需求：给定一段文本，从中找到某个指定的关键字。

一般来说，我们完成这个目标，会直接去调用 C 语言提供的strstr()函数。但是这个函数的算法是暴力穷举去匹配，时间复杂度很高：

1.jpg

在串的模式匹配中，已经有人帮我们设计出了高效的算法，这就是KMP：

2.jpg

它的关键是用动态规划的知识构造一个关于 Pattern 的 Prefix Table （前缀表），然后根据 Prefix Table 来快速匹配字符串。

最长公共前后缀

给定一个字符串ababc，它的子串前缀、子串后缀和最长公共前后缀的长度如下：

子串 字串前缀 字串后缀 最长公共前后缀 的 长度
a a NULL 0
ab a b 0
aba a、ab a、ba 1
abab a、ab、aba b、ab、bab 2
ababc a、ab、aba、abab c、bc、abc、babc 0

把最长公共前后缀的长度专门组成一个数组，这就是 Prefix Table。在大部分教科书中，会把 Prefix Table 的第一个元素置为-1。如上述例子的 Prefix Table 会是[-1, 0, 0, 1, 2]。

Prefix Table 的构建

算法步骤如下：

  1. 定义一个一维数组，名为prefix_table，其长度和 Pattern 相同（prefix_table[size]）；
  2. 定义变量i和j，设置i = 0、j = 1、prefix_table[0] = 0；
  3. 比较pattern[i]和pattern[j]；
  4. 如果pattern[i] == pattern[j]，则设置prefix_table[j] = i + 1;并且i += 1; j += 1;，之后返回步骤三；
  5. 如果pattern[i] != pattern[j]，则检查i的值。如果i == 0，则设置prefix_table[j] = 0;并j += 1;。如果i != 0，则设置i = prefix_table[i-1];。返回步骤三；
  6. 重复上述步骤直到prefix_table被填满；

Rust代码实现如下：

  1. // src/lib.rs
  2. pub fn build_prefix_table(pattern: &str) -> Vec<usize> {
  3.     let mut prefix_table = vec![0];
  4.     let pattern = pattern.as_bytes();
  6.     let mut i = 0;
  7.     let mut j = 1;
  8.     while j < pattern.len() {
  9.         if pattern[i] == pattern[j] {
  10.             prefix_table.push(i + 1);
  11.             i += 1;
  12.             j += 1;
  13.         } else {
  14.             if i == 0 {
  15.                 prefix_table.push(0);
  16.                 j += 1;
  17.             } else {
  18.                 i = prefix_table[i - 1];
  19.             }
  20.         }
  21.     }
  23.     return prefix_table;
  24. }

使用 Prefix Table 匹配字符串

假设有 Text：abaacababcac，Pattern：abab。我们已知前缀表prefix = [0, 0, 1, 2]，匹配过程如下：

2-1.jpg

第一步：开始匹配，到第三个字符匹配失败。我们从匹配失败的地方把 Pattern 指针由2拉到prefix[2] = 1。

2-2.jpg

第二步：匹配依旧失败，我们从匹配失败的地方把 Pattern 指针由1拉到prefix[1] = 0。

2-3.jpg

第三步：匹配到第二个字符失败，重复前面的步骤，从匹配失败的地方，把 Pattern 指针由1拉到prefix[1] = 0处。

2-4.jpg

第四步：匹配失败，把 Pattern 指针由1拉到0：

2-5.jpg

第五步：依旧失败，此时 Pattern 指针已经是0了，我们把 Text 指针向后移动一格，继续匹配后面的字符。

2-6.jpg

第六步：此时出现了一个匹配成功的序列。我们记录下当前的位置。把 Pattern 指针置为prefix[i-1]，并把 Text 指针后移一格，寻找后面有没有更多能匹配上的字符串。

2-7.jpg

此时 Pattern 的尾巴已经碰到 Text 的尾巴了，没有找到更多能匹配上的字符。匹配过程结束。

Rust代码实现如下：

  1. // src/lib.rs
  2. pub fn kmp(text: &str, pattern: &str) -> Option<Vec<usize>> {
  3.     if text.is_empty() || pattern.is_empty() {
  4.         return None;
  5.     }
  7.     let prefix_table = build_prefix_table(pattern);
  8.     let text = text.as_bytes();
  9.     let pattern = pattern.as_bytes();
  11.     let mut index_pattern = 0;
  12.     let mut ret = vec![];
  13.     for (index_text, &item) in text.iter().enumerate() {
  14.         while index_pattern > 0 && item != pattern[index_pattern] {
  15.             index_pattern = prefix_table[index_pattern - 1];
  16.         }
  18.         if item == pattern[index_pattern] {
  19.             index_pattern += 1; // next char matched, increment position
  20.             if index_pattern == pattern.len() {
  21.                 ret.push(index_text - index_pattern + 1);
  22.                 index_pattern = prefix_table[index_pattern - 1];
  23.             }
  24.         }
  25.     }
  27.     if ret.is_empty() {
  28.         return None;
  29.     }
  30.     Some(ret)
  31. }

测试代码如下：

  1. #[cfg(test)]
  2. mod tests {
  3.     use super::*;
  5.     #[test]
  6.     fn prefix_table_works() {
  7.         assert_eq!(build_prefix_table("ababc"), vec![0, 0, 1, 2, 0]);
  8.         assert_eq!(build_prefix_table("ABCDABD"), vec![0, 0, 0, 0, 1, 2, 0]);
  9.         assert_eq!(build_prefix_table("abaabc"), vec![0, 0, 1, 1, 2, 0]);
  10.         assert_eq!(build_prefix_table("aaaaa"), vec![0, 1, 2, 3, 4]);
  11.         assert_eq!(build_prefix_table("ababab"), vec![0, 0, 1, 2, 3, 4]);
  12.         assert_eq!(build_prefix_table("abacabab"), vec![0, 0, 1, 0, 1, 2, 3, 2]);
  13.         assert_eq!(
  14.             build_prefix_table("aaabaaaaab"),
  15.             vec![0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
  16.         );
  17.     }
  19.     #[test]
  20.     fn kmp_works() {
  21.         assert_eq!(kmp("", ""), None);
  22.         assert_eq!(kmp("", "hello"), None);
  23.         assert_eq!(kmp("hello", ""), None);
  24.         assert_eq!(kmp("abaacababcac", "abab"), Some(vec![5]));
  25.         assert_eq!(kmp("cbabcababcac", "ab"), Some(vec![2, 5, 7]));
  26.         assert_eq!(kmp("cbabcababcac", "apple"), None);
  27.     }
  28. }

运行结果如下：

  1. WSL my_kmp on 🌱 main [?] is 📦 v0.1.0 via 🦀 v1.55.0
  2. ❯ cargo t
  3.     Finished test [unoptimized + debuginfo] target(s) in 0.01s
  4.      Running unittests (target/debug/deps/my_kmp-f74484c2e47d7d4c)
  6. running 2 tests
  7. test tests::kmp_works ... ok
  8. test tests::prefix_table_works ... ok
  10. test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
  12.    Doc-tests my_kmp
  14. running 0 tests
  16. test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

参考资料