Rust语言Sunday算法实现（从零开始掌握高效字符串匹配）

Sunday算法的核心原理

假设我们要在文本 text 中查找模式串 pattern：

1. 从左到右逐个字符比对 pattern 和 text 的对应位置。
2. 如果发现不匹配，就查看 text 中“当前窗口右侧下一个字符”（即 text[i + pattern.len()]）。
3. 根据该字符在 pattern 中最后一次出现的位置，决定模式串向右跳过的距离。
4. 如果该字符不在 pattern 中，则直接跳过整个模式串长度 + 1。

为了快速判断跳转距离，我们需要预先构建一个“偏移表”（shift table），记录每个字符在 pattern 中最右边出现的位置（从右往左数的索引）。

用Rust实现Sunday算法

下面，我们一步步用Rust编写Sunday算法。Rust的安全性和性能使其成为实现此类算法的理想选择。

第1步：构建偏移表

首先，我们需要一个函数来生成偏移表。这个表将告诉我们，当遇到某个字符时，模式串应该向右移动多少位。

use std::collections::HashMap;fn build_shift_table(pattern: &str) -> HashMap<char, usize> {    let mut shift_table = HashMap::new();    let len = pattern.len();        // 默认偏移量为 pattern 长度 + 1    for c in pattern.chars() {        shift_table.insert(c, len + 1);    }        // 从右往左遍历，更新每个字符的偏移量    for (i, c) in pattern.chars().enumerate() {        // 偏移量 = 模式长度 - 当前索引        shift_table.insert(c, len - i);    }        shift_table}

注意：这里我们使用 len - i 作为偏移值，因为当在文本中看到字符 c 时，我们希望将 pattern 中最右边的 c 对齐到该位置。

第2步：实现主匹配函数

接下来，我们编写主函数 sunday_search，它返回所有匹配的起始索引。

fn sunday_search(text: &str, pattern: &str) -> Vec<usize> {    if pattern.is_empty() {        return vec![0];    }        let text_chars: Vec<char> = text.chars().collect();    let pattern_chars: Vec<char> = pattern.chars().collect();    let text_len = text_chars.len();    let pattern_len = pattern_chars.len();        if pattern_len > text_len {        return vec![];    }        let shift_table = build_shift_table(pattern);    let default_shift = pattern_len + 1;    let mut matches = Vec::new();    let mut i = 0; // text 中的起始索引        while i <= text_len - pattern_len {        // 检查当前窗口是否匹配        let mut matched = true;        for j in 0..pattern_len {            if text_chars[i + j] != pattern_chars[j] {                matched = false;                break;            }        }                if matched {            matches.push(i);        }                // 计算下一次跳转位置        let next_char_index = i + pattern_len;        if next_char_index < text_len {            let next_char = text_chars[next_char_index];            let shift = *shift_table.get(&next_char).unwrap_or(&default_shift);            i += shift;        } else {            break;        }    }        matches}

第3步：测试我们的实现

让我们写一个简单的测试用例：

fn main() {    let text = "hello world, hello rust";    let pattern = "hello";        let indices = sunday_search(text, pattern);    println!("Found \"{}\" at indices: {:?}", pattern, indices);    // 输出: Found "hello" at indices: [0, 13]}

为什么选择Sunday算法？

在众多Rust字符串匹配算法中，Sunday算法因其简洁性和良好平均性能脱颖而出。它不需要复杂的预处理（如KMP的失败函数），也不依赖大量内存（如后缀数组）。对于大多数日常应用场景，Sunday算法提供了极佳的性能与代码可读性平衡。

总结

通过本篇Rust编程教程，你已经掌握了如何用Rust实现Sunday算法。这不仅提升了你的Rust高效搜索能力，也为理解更复杂的字符串算法打下了基础。记住，算法的核心在于理解其思想，而Rust的类型安全和内存安全特性，能让你在实现过程中避免许多常见错误。

现在，你可以尝试优化这个实现（例如使用数组代替HashMap以提升速度），或者将其封装成一个库供他人使用。Happy coding in Rust!