深入理解KMP算法（用Rust语言高效实现字符串匹配）

什么是KMP算法？

KMP算法由Donald Knuth、Vaughan Pratt和James H. Morris于1977年提出，其核心思想是：当发生不匹配时，利用已匹配部分的信息，避免从头开始重新比较。这大大减少了不必要的字符比较次数，从而提升效率。

与暴力匹配（Brute Force）不同，KMP通过预处理模式串（pattern），构建一个称为前缀函数（也叫“失败函数”或“next数组”）的辅助数组，用于指导主串（text）指针在失配后应跳转到的位置。

KMP算法的两个关键步骤

1. 构建前缀函数（Prefix Function）：分析模式串，找出每个位置的最长相等真前缀与真后缀的长度。
2. 执行匹配过程：利用前缀函数，在主串中高效滑动模式串进行匹配。

第一步：构建前缀函数

前缀函数 π[i] 表示模式串 pattern[0..i] 中，最长的相等真前缀与真后缀的长度（且不能等于整个子串本身）。

举个例子，对于模式串 "ABABC"：

• i=0: "A" → 无真前缀/后缀 → π[0] = 0
• i=1: "AB" → 前缀[A], 后缀[B] → 不相等 → π[1] = 0
• i=2: "ABA" → 前缀[A, AB], 后缀[A, BA] → 最长相等的是 "A" → π[2] = 1
• i=3: "ABAB" → 最长相等真前后缀是 "AB" → π[3] = 2
• i=4: "ABABC" → 无相等 → π[4] = 0

现在，我们用 Rust 来实现这个前缀函数：

fn build_prefix_function(pattern: &str) -> Vec<usize> {    let chars: Vec<char> = pattern.chars().collect();    let n = chars.len();    let mut pi = vec![0; n];    let mut j = 0;    for i in 1..n {        while j > 0 && chars[i] != chars[j] {            j = pi[j - 1];        }        if chars[i] == chars[j] {            j += 1;        }        pi[i] = j;    }    pi}

第二步：执行KMP匹配

有了前缀函数后，我们就可以在主串中高效地搜索模式串了。主逻辑如下：

• 使用两个指针 i（主串）和 j（模式串）。
• 若当前字符匹配，则两个指针都前进。
• 若不匹配且 j > 0，则 j 回退到 π[j-1]；否则 i 前进。
• 当 j 等于模式串长度时，说明找到一个匹配，记录位置并回退 j。

下面是完整的 Rust KMP算法 实现：

fn kmp_search(text: &str, pattern: &str) -> Vec<usize> {    if pattern.is_empty() {        return vec![];    }    let text_chars: Vec<char> = text.chars().collect();    let pattern_chars: Vec<char> = pattern.chars().collect();    let pi = build_prefix_function(pattern);    let mut matches = Vec::new();    let mut j = 0; // 模式串指针    for i in 0..text_chars.len() {        while j > 0 && text_chars[i] != pattern_chars[j] {            j = pi[j - 1];        }        if text_chars[i] == pattern_chars[j] {            j += 1;        }        if j == pattern_chars.len() {            // 找到匹配，起始位置为 i - j + 1            matches.push(i - j + 1);            j = pi[j - 1]; // 继续寻找下一个匹配        }    }    matches}

完整示例与测试

将上述函数组合起来，并编写一个简单的测试：

fn main() {    let text = "ABABDABACDABABCABCABC";    let pattern = "ABABC";    let positions = kmp_search(text, pattern);    println!("匹配位置: {:?}", positions); // 输出: [10]    // 测试前缀函数    let pi = build_prefix_function(pattern);    println!("前缀函数: {:?}", pi); // 输出: [0, 0, 1, 2, 0]}

为什么选择Rust实现KMP？

Rust语言以其内存安全、零成本抽象和高性能著称，非常适合实现底层算法。通过使用 Vec<char> 和借用机制，我们既能保证安全性，又能获得接近C/C++的性能。此外，Rust的类型系统帮助我们在编译期就避免许多常见错误，比如越界访问——这在手动管理指针的语言中非常容易出错。

总结

通过本教程，我们详细讲解了 KMP模式匹配 Rust实现 的全过程，包括前缀函数的构建和主匹配逻辑。KMP算法虽然初看有些抽象，但一旦理解其“利用已匹配信息跳过无效比较”的思想，就会发现它非常优雅。

无论你是准备面试，还是想提升 高效字符串搜索 Rust 能力，掌握KMP都是值得的。希望这篇教程能帮助你从零开始理解并实现这一经典算法！

如果你觉得有帮助，不妨动手敲一遍代码，加深理解。编程之路，贵在实践！