Rust语言BM算法实现（从零开始掌握Boyer-Moore字符串搜索算法）

核心思想：坏字符规则与好后缀规则

1. 坏字符规则（Bad Character Rule）：当发生不匹配时，查看文本中导致不匹配的“坏字符”。如果该字符在模式串中出现过，则将模式串对齐到该字符最后一次出现的位置；否则，直接跳过整个模式串长度。

2. 好后缀规则（Good Suffix Rule）：当部分后缀匹配成功但前一个字符不匹配时，利用已匹配的“好后缀”在模式串中的其他出现位置进行对齐。

为简化教学，本教程先实现仅使用坏字符规则的 BM 算法，它已经能显著提升性能，且逻辑清晰易于理解。

第一步：构建坏字符表（Bad Character Table）

我们需要一个哈希表（或数组），记录模式串中每个字符最后一次出现的位置（从0开始计数）。这样在匹配失败时，可以快速查到应跳过的距离。

// 构建坏字符表fn build_bad_char_table(pattern: &str) -> std::collections::HashMap<char, usize> {    let mut table = std::collections::HashMap::new();    for (i, ch) in pattern.chars().enumerate() {        // 记录每个字符最后一次出现的位置        table.insert(ch, i);    }    table}

第二步：实现 BM 搜索主函数

主函数从文本的起始位置开始，每次尝试匹配整个模式串。若匹配失败，根据坏字符表计算跳转距离，并移动模式串位置。

fn boyer_moore_search(text: &str, pattern: &str) -> Option<usize> {    if pattern.is_empty() {        return Some(0);    }    let bad_char_table = build_bad_char_table(pattern);    let text_chars: Vec<char> = text.chars().collect();    let pattern_chars: Vec<char> = pattern.chars().collect();    let m = pattern_chars.len();    let n = text_chars.len();    let mut shift = 0; // 当前模式串在文本中的起始位置    while shift <= n - m {        let mut j = m - 1; // 从模式串末尾开始比较        // 从右向左匹配        while j >= 0 && pattern_chars[j] == text_chars[shift + j] {            if j == 0 { break; }            j -= 1;        }        if j == 0 && pattern_chars[0] == text_chars[shift] {            // 完全匹配            return Some(shift);        } else {            // 匹配失败，计算跳转距离            let bad_char = text_chars[shift + m - 1];            let bad_char_pos = *bad_char_table.get(&bad_char).unwrap_or(&usize::MAX);            // 跳过距离 = 模式长度 - 坏字符在模式中的位置 - 1            let skip = if bad_char_pos < m - 1 {                m - 1 - bad_char_pos            } else {                1            };            shift += skip;        }    }    None // 未找到}

第三步：编写测试用例

让我们验证一下我们的 Rust BM算法实现是否正确：

fn main() {    let text = "Hello, welcome to the world of Rust programming!";    let pattern = "Rust";    match boyer_moore_search(text, pattern) {        Some(index) => println!("Found '{}' at index {}", pattern, index),        None => println!("'{}' not found", pattern),    }    // 测试未找到的情况    let pattern2 = "Python";    match boyer_moore_search(text, pattern2) {        Some(index) => println!("Found '{}' at index {}", pattern2, index),        None => println!("'{}' not found", pattern2),    }}

为什么选择 Rust 实现 BM 算法？

Rust 的零成本抽象、内存安全保证以及优秀的性能表现，使其成为实现底层算法的理想语言。通过本教程，你不仅掌握了 Rust字符串搜索的核心技巧，也深入理解了 BM 算法的工作原理。

进阶建议

- 尝试加入好后缀规则以进一步提升性能
- 使用 Vec<u8> 处理 ASCII 字符串以避免 Unicode 开销
- 对比 Rust 标准库的 .find() 方法，分析性能差异

希望这篇 BM算法教程能帮助你迈出 Rust 高效字符串处理的第一步！动手写一写，你会发现 Rust 既强大又友好。