极速字符串匹配：Sunday算法的Rust实现（从零开始掌握高效文本查找）

什么是 Sunday 算法？

Sunday 算法是一种高效的单模式字符串匹配算法，由 Daniel M. Sunday 在 1990 年提出。它的核心思想是：当发生不匹配时，不仅看当前比较位置，还看主串中“下一个即将参与比较的字符”，从而决定跳过多远。

相比 KMP 或 Boyer-Moore，Sunday 算法更简单、平均性能更好，尤其适合实际文本中的短模式匹配。这也是为什么它常被用于高性能文本处理场景。

算法原理简述

假设我们要在主串 haystack 中查找模式串 needle：

1. 将 needle 与 haystack 的起始位置对齐。
2. 从左到右逐字符比较。
3. 如果全部匹配，返回起始索引。
4. 如果某处不匹配，查看 haystack 中“当前窗口右边第一个字符”（即 haystack[i + needle.len()]）。
5. 根据该字符在 needle 中最后一次出现的位置，决定向右滑动的距离。若未出现，则直接跳过整个窗口长度 + 1。

用 Rust 实现 Sunday 算法

下面我们一步步用 Rust 编写这个算法。我们将构建一个函数 sunday_search，它接收两个字符串切片，并返回匹配的起始索引（Option）。

fn sunday_search(haystack: &str, needle: &str) -> Option<usize> {    // 处理边界情况    if needle.is_empty() {        return Some(0);    }    if haystack.len() < needle.len() {        return None;    }    let haystack_bytes = haystack.as_bytes();    let needle_bytes = needle.as_bytes();    let n = haystack_bytes.len();    let m = needle_bytes.len();    // 构建偏移表（shift table）    // 对于 ASCII 字符，我们可以用长度为 256 的数组    let mut shift = [m as u8 + 1; 256];    for (i, &b) in needle_bytes.iter().enumerate() {        shift[b as usize] = (m - i) as u8;    }    let mut i = 0; // 主串当前窗口起始位置    while i <= n - m {        // 尝试匹配        if &haystack_bytes[i..i + m] == needle_bytes {            return Some(i);        }        // 查看窗口右侧下一个字符        if i + m < n {            let next_char = haystack_bytes[i + m] as usize;            i += shift[next_char] as usize;        } else {            break;        }    }    None}

代码详解

• 边界处理：空模式串应返回 0；主串比模式串短则无解。
• 字节切片：Rust 的 str 是 UTF-8 编码，但我们这里假设只处理 ASCII（或单字节字符），所以转为 &[u8] 更高效。
• 偏移表（shift table）：这是 Sunday 算法的核心。我们用一个长度为 256 的数组记录每个字节值在 needle 中“从右往左”第一次出现时距离末尾的距离。未出现的字符默认跳过 m+1 位。
• 主循环：每次尝试匹配，失败后根据右侧字符查表跳转。

测试我们的实现

让我们写一个简单的测试来验证功能：

fn main() {    let text = "Hello, welcome to the world of Rust!";    let pattern = "Rust";    match sunday_search(text, pattern) {        Some(index) => println!("Found '{}' at index {}", pattern, index),        None => println!("'{}' not found", pattern),    }    // 测试未找到的情况    assert_eq!(sunday_search("abc", "d"), None);    // 测试空模式    assert_eq!(sunday_search("anything", ""), Some(0));}

运行后你应该看到输出：Found 'Rust' at index 30。

性能与适用场景

Sunday 算法在平均情况下的时间复杂度接近 O(n/m)，最坏情况为 O(nm)，但在实际文本（如英文、日志）中表现优异。它特别适合以下场景：

• 短模式串（如关键词、命令）的快速查找
• 内存受限环境（只需一个 256 字节的表）
• 需要简单、可维护的高性能匹配逻辑

通过本次教程，你不仅学会了 Rust字符串搜索 的一种高效方法，也掌握了 Sunday算法实现 的核心思想。这种 Rust高效匹配 技巧可以用于日志分析、文本编辑器、网络协议解析等场景。希望你能将所学应用到实际项目中，体验 字符串查找算法 带来的性能提升！

提示：本实现假设输入为 ASCII 字符。若需支持 Unicode，需改用字符迭代或更复杂的偏移策略。