当前位置：首页 > news >正文

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

news 2026/6/13 21:33:53

在文本处理、搜索引擎、代码编辑器等众多场景中，快速查找子字符串是一项基础而关键的操作。Rust 作为一种内存安全且高性能的系统编程语言，非常适合实现高效的字符串搜索算法。本文将带你从零开始，用 Rust 实现经典的Boyer-Moore（BM）算法，即使你是 Rust 新手，也能轻松理解并动手实践。

什么是 Boyer-Moore 算法？

Boyer-Moore（BM）算法是一种高效的字符串匹配算法，由 Robert S. Boyer 和 J Strother Moore 在 1977 年提出。与朴素的逐字符比较不同，BM 算法通过从右向左匹配模式串，并利用两个启发式规则（坏字符规则和好后缀规则）来跳过大量不必要的比较，从而在实践中往往比 KMP 等算法更快，尤其适用于长文本搜索。

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

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), }}