Rust语言实现RK算法（Rabin-Karp字符串匹配算法详解）

什么是RK算法？

RK算法由Michael O. Rabin和Richard M. Karp于1987年提出，其核心思想是利用哈希函数对模式串（pattern）和文本串（text）的子串进行快速比较。如果两个字符串的哈希值相同，则再逐字符验证是否真正相等，从而减少不必要的字符比较。

该算法的时间复杂度平均为O(n + m)，其中n是文本长度，m是模式长度，非常适合在大量文本中查找多个模式。

为什么用Rust实现？

Rust语言以其内存安全、零成本抽象和高性能著称，非常适合实现底层算法。使用Rust编写RK算法不仅能保证效率，还能避免常见的内存错误（如缓冲区溢出），是学习系统编程和算法实现的理想选择。

实现步骤详解

我们将按以下步骤实现RK算法：

1. 定义哈希函数（使用滚动哈希）
2. 计算模式串的哈希值
3. 滑动窗口遍历文本串，计算每个子串的哈希值
4. 哈希匹配时，进行逐字符验证

完整Rust代码实现

以下是完整的RK算法Rust实现：

// 引入标准库use std::collections::HashSet;// 定义常量const PRIME: u64 = 101; // 一个较小的质数，用于哈希计算/// 计算字符串的哈希值fn hash(s: &str) -> u64 {    let mut hash_value = 0u64;    let len = s.len() as u64;    for (i, c) in s.chars().enumerate() {        // 使用公式: hash = (c * PRIME^(len - i - 1)) mod some_large_prime        // 为简化，我们直接累加 c * PRIME^i        hash_value = (hash_value * PRIME + (c as u64)) % u64::MAX;    }    hash_value}/// 滚动哈希：从旧哈希值计算新哈希值fn rolling_hash(    old_hash: u64,    old_char: char,    new_char: char,    pattern_len: usize,) -> u64 {    let high_order = (old_char as u64)        .wrapping_mul(PRIME.pow((pattern_len - 1) as u32));    let new_hash = (old_hash        .wrapping_sub(high_order)        .wrapping_mul(PRIME)        .wrapping_add(new_char as u64))        % u64::MAX;    new_hash}/// RK算法主函数fn rabin_karp(text: &str, pattern: &str) -> Vec {    if pattern.is_empty() || text.is_empty() || pattern.len() > text.len() {        return vec![];    }    let pattern_len = pattern.len();    let text_chars: Vec = text.chars().collect();    let pattern_chars: Vec = pattern.chars().collect();    let pattern_hash = hash(pattern);    let mut text_hash = hash(&text[..pattern_len]);    let mut matches = Vec::new();    // 检查第一个窗口    if text_hash == pattern_hash         && text_chars[..pattern_len] == pattern_chars[..] {        matches.push(0);    }    // 滑动窗口    for i in 1..=(text.len() - pattern_len) {        // 计算新哈希        text_hash = rolling_hash(            text_hash,            text_chars[i - 1],            text_chars[i + pattern_len - 1],            pattern_len,        );        // 哈希匹配则逐字符验证        if text_hash == pattern_hash {            let start = i;            let end = i + pattern_len;            if text_chars[start..end] == pattern_chars[..] {                matches.push(i);            }        }    }    matches}// 测试函数fn main() {    let text = "ABABDABACDABABCABCABC";    let pattern = "ABABC";    let positions = rabin_karp(text, pattern);    println!("Pattern found at positions: {:?}", positions);}

代码说明

• hash 函数：计算字符串初始哈希值。
• rolling_hash 函数：利用前一个窗口的哈希值快速计算下一个窗口的哈希值，这是RK算法高效的关键。
• rabin_karp 函数：主逻辑，返回所有匹配位置的索引。
• 使用 wrapping_mul 和 wrapping_sub 避免除零或溢出 panic（Rust的安全特性）。

运行与测试

将上述代码保存为 rk.rs，然后在终端运行：

rustc rk.rs
./rk

你将看到输出：

Pattern found at positions: [10]

总结

通过本教程，你已经学会了如何用Rust语言实现RK算法（Rabin-Karp算法），这是一种高效的字符串匹配方法。掌握此算法不仅有助于面试准备，还能提升你在文本处理、数据挖掘等领域的实战能力。

希望这篇教程对你有帮助！如果你喜欢，请分享给更多学习Rust语言和算法的朋友。