用 Rabin-Karp 滚动哈希查找子串

功能说明

Rabin-Karp 通过滚动哈希在文本中查找模式串：先计算模式串和第一个窗口的哈希，然后每次右移一位只减去移出的字符、加入新字符，平均时间复杂度接近线性。

这段代码返回所有匹配位置，适合在日志、文档或 DNA 序列中做多次子串搜索。哈希命中后仍会逐字符比较，确保哈希碰撞不会产生误报。

关键代码

find_all 先把字符串转成 Vec<char>，这样返回的位置是字符下标而不是字节下标，避免 UTF-8 多字节字符导致位置错乱。BASE 取 257，highest 保存 BASE^(m-1)，用于移除窗口最左字符。

初始哈希通过 Horner 法则计算；滑动窗口时用 wrapping_sub 和 wrapping_mul 模拟模 2^64 运算。只有当哈希相等且切片逐字符相等时才记录位置。

使用注意

返回值是字符下标，不是字节偏移；如果需要用于字符串切片，必须再把字符下标换算成字节位置。哈希使用 64 位回绕运算，碰撞概率很低但并非为零，因此逐字符校验不可省略。

最坏情况下（大量重复模式）仍可能退化到 O(n*m)。空模式返回空列表，这是刻意的约定；如果业务认为空模式匹配每个位置，需要单独处理。模式长度超过文本时直接返回空，避免下标下溢。

验证方式

示例断言 abracadabra 中 abra 出现在位置 0 和 7，aaaa 中 aa 出现在 0、1、2，模式比文本长或为空时返回空列表。可以再加入中文文本，确认返回的是字符位置而不是字节位置，并用重复字符测试碰撞校验路径。

代码示例

fn find_all(haystack: &str, needle: &str) -> Vec<usize> {
    let hay: Vec<char> = haystack.chars().collect();
    let pattern: Vec<char> = needle.chars().collect();
    if pattern.is_empty() || pattern.len() > hay.len() {
        return Vec::new();
    }

    const BASE: u64 = 257;
    let mut highest = 1u64;
    for _ in 1..pattern.len() {
        highest = highest.wrapping_mul(BASE);
    }

    let mut pattern_hash = 0u64;
    let mut window_hash = 0u64;
    for index in 0..pattern.len() {
        pattern_hash = pattern_hash
            .wrapping_mul(BASE)
            .wrapping_add(pattern[index] as u64);
        window_hash = window_hash
            .wrapping_mul(BASE)
            .wrapping_add(hay[index] as u64);
    }

    let mut matches = Vec::new();
    for start in 0..=hay.len() - pattern.len() {
        if window_hash == pattern_hash && hay[start..start + pattern.len()] == pattern[..] {
            matches.push(start);
        }
        if start + pattern.len() < hay.len() {
            window_hash = window_hash
                .wrapping_sub((hay[start] as u64).wrapping_mul(highest));
            window_hash = window_hash
                .wrapping_mul(BASE)
                .wrapping_add(hay[start + pattern.len()] as u64);
        }
    }
    matches
}

fn main() {
    assert_eq!(find_all("abracadabra", "abra"), vec![0, 7]);
    assert_eq!(find_all("aaaa", "aa"), vec![0, 1, 2]);
    assert_eq!(find_all("short", "longer pattern"), Vec::<usize>::new());
    assert_eq!(find_all("anything", ""), Vec::<usize>::new());
    println!("{:?}", find_all("abracadabra", "abra"));
}