高效字符串匹配：Rust语言KMP算法详解（从零实现KMP模式匹配）

什么是KMP算法？

KMP算法是一种线性时间复杂度的字符串匹配算法，由 Donald Knuth、Vaughan Pratt 和 James H. Morris 于1977年共同提出。与暴力匹配（Brute Force）不同，KMP通过预处理模式串（pattern），构建一个“部分匹配表”（也称 next 数组或 failure function），从而在匹配失败时跳过不必要的比较，将时间复杂度从 O(n×m) 优化到 O(n + m)，其中 n 是主串长度，m 是模式串长度。

KMP的核心思想：利用已匹配信息

假设我们在主串 "ABABABC" 中查找模式串 "ABABC"。当匹配到第5个字符时发现不匹配（主串是 'A'，模式串期望是 'C'）。暴力方法会回退主串指针重新开始，但KMP知道：前面已经匹配了 "ABAB"，而 "ABAB" 的最长相等前后缀是 "AB"（长度为2），因此可以直接将模式串向右滑动，使模式串的第3个字符（索引2）对齐当前主串位置，继续匹配。

这个“最长相等前后缀”的长度信息，就存储在我们常说的 前缀函数（prefix function）或 next数组 中。

步骤一：构建前缀函数（Prefix Function）

前缀函数 π[i] 表示模式串 s[0..i] 中，最长的既是真前缀又是真后缀的子串长度。

例如，模式串 "ABABC" 的前缀函数为：

i     : 0 1 2 3 4s[i]  : A B A B Cπ[i]  : 0 0 1 2 0

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

fn compute_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 k = 0;    for q in 1..n {        while k > 0 && chars[k] != chars[q] {            k = pi[k - 1];        }        if chars[k] == chars[q] {            k += 1;        }        pi[q] = k;    }    pi}

步骤二：使用前缀函数进行匹配

有了前缀函数，我们就可以高效地在主串中搜索模式串了。主串指针永不回退，匹配失败时根据前缀函数跳转模式串指针。

以下是完整的 KMP 匹配函数实现：

fn kmp_search(text: &str, pattern: &str) -> Option<usize> {    if pattern.is_empty() {        return Some(0);    }    let text_chars: Vec<char> = text.chars().collect();    let pattern_chars: Vec<char> = pattern.chars().collect();    let pi = compute_prefix_function(pattern);    let mut q = 0; // 当前匹配长度    for (i, &c) in text_chars.iter().enumerate() {        while q > 0 && pattern_chars[q] != c {            q = pi[q - 1];        }        if pattern_chars[q] == c {            q += 1;        }        if q == pattern_chars.len() {            // 找到匹配，返回起始索引            return Some(i + 1 - q);        }    }    None // 未找到}

完整示例与测试

让我们把所有代码整合起来，并写一个简单的测试：

fn main() {    let text = "ABABABCABABABD";    let pattern = "ABABC";    match kmp_search(text, pattern) {        Some(index) => println!("Pattern found at index: {}", index),        None => println!("Pattern not found"),    }}// 输出：Pattern found at index: 2

为什么选择Rust实现KMP？

Rust 以其内存安全、零成本抽象和高性能著称，非常适合实现底层算法。通过使用 Vec<char>，我们避免了UTF-8字节索引的复杂性（虽然牺牲了一点性能，但提高了可读性）。在实际生产环境中，你也可以选择基于字节（&[u8]）的实现以获得更高效率，尤其当处理ASCII文本时。

总结

通过本文，你已经学会了如何在 Rust 中从零实现 KMP算法。我们讲解了前缀函数的构建逻辑、匹配过程，并提供了完整可运行的代码。掌握 字符串匹配 技术不仅能提升你的算法能力，也为处理文本数据打下坚实基础。

记住，KMP的核心在于“**不要重复检查已知信息**”。这也是许多高效算法的共同哲学。

希望这篇教程能帮助你理解 Rust KMP算法、字符串匹配、Rust字符串处理 以及 KMP模式匹配 的核心概念。动手试试吧！