如何用Rust标准库高效查找切片在另一切片中的索引？

在JavaScript中，我们可以通过"abcde".indexOf("de") === 3快速查找子串的起始索引。现在需要在Rust中，对实现了PartialEq trait的&[T]切片完成同样的功能，示例需求如下：

fn search_haystack<T: PartialEq>(needle: &[T], haystack: &[T]) -> Option<usize> {
    todo!()
}

fn main() {
    let haystack = [1,2,3,4,5];
    let needle = [3,4];
    assert_eq!(search_haystack(&needle, &haystack), Some(2));
}

不想自行实现基础逻辑，希望用稳定版标准库的高效方案解决。

解决方案 #

Rust稳定版标准库中没有直接提供类似indexOf的内置方法，但可以通过slice::windows方法高效实现这个功能，这是标准库原生的稳定API，逻辑简洁且性能可靠。

实现思路

• 先处理边界情况：如果needle为空切片，按惯例返回Some(0)（可根据需求调整）；如果haystack长度小于needle，直接返回None。
• 使用haystack.windows(needle.len())迭代haystack中所有长度与needle一致的子切片窗口。
• 对每个窗口枚举其起始索引，找到第一个与needle相等的窗口，返回对应的索引。

完整实现代码

fn search_haystack<T: PartialEq>(needle: &[T], haystack: &[T]) -> Option<usize> {
    let needle_len = needle.len();
    let haystack_len = haystack.len();

    // 边界情况处理
    if needle_len == 0 {
        return Some(0); // 空匹配默认返回起始索引0，可按需修改
    }
    if haystack_len < needle_len {
        return None;
    }

    // 遍历匹配窗口，查找第一个匹配项
    haystack
        .windows(needle_len)
        .enumerate()
        .find(|(_, window)| window == &needle)
        .map(|(index, _)| index)
}

fn main() {
    let haystack = [1,2,3,4,5];
    let needle = [3,4];
    assert_eq!(search_haystack(&needle, &haystack), Some(2));

    // 额外测试用例
    assert_eq!(search_haystack(&[], &[1,2,3]), Some(0));
    assert_eq!(search_haystack(&[6], &[1,2,3]), None);
    assert_eq!(search_haystack(&[1,2], &[1,2,1,2]), Some(0));
}

补充说明

• windows方法生成的是原切片的视图，不会额外分配内存，性能开销极低。
• 对于大部分常规场景，这种实现的效率已经足够；如果需要处理超大规模切片并追求极致性能，可以自行实现KMP等更高效的匹配算法，但标准库的windows方案是最简洁的稳定版选择。

内容的提问来源于stack exchange，提问作者nlta