algorithm - Rust - 如何在 vec 中搜索子集 - 并找到 subvec 的起始索引？

Question

如果我有一个 vec，我如何搜索它以查找它是否包含另一个 vec - 并返回此 subvec 开始的索引？

let mut haystack = vec!(0, 0, 0, 1, 48, 120, 49, 49, 1, 0);
let mut needle = vec!(48, 120, 49, 49);

这样它会返回 4(原始子集的起始索引)(或者更确切地说，在这种情况下它会返回一个包含 4 的结果 - 如果根本找不到它就会出错)。

Answer 1

这是经典string search problem . @Willem Van Onsem 建议使用 KMP 算法，但您应该从朴素算法开始。

对于 haystack 的每个索引，尝试将与 needle 相同长度并从 haystack 中的该索引开始的字符串与 needle 本身。

看看这个:

0   0   0   1   48  120 49  49  1   0
48  120 49  49
x fail
    48  120 49  49
    x fail
        48  120 49  49
        x fail
            48  120 49  49
            x fail
                48  120 49  49
                -   -   -   - match!

x表示元素不同，-表示元素相同。在每个 x 上，移动到 haystack 的下一个元素(这是与 KMP 的区别，KMP 可能一次移动多个元素)。

在 Rust 中，您将编写如下内容:

fn find1(haystack: &Vec<i32>, needle: &Vec<i32>) -> i64 {
    for i in 0..haystack.len()-needle.len()+1 { // last indices of haystack are too far right to get a match
        let mut j = 0;
        while j < needle.len() { // check every char of needle
            if needle[j] != haystack[i+j] { // doesn't match
                break; // try the next i
            }
            j += 1; // else: match so far
        }
        if j == needle.len() { // no break: a full match was found
            return i as i64;
        }
    }
    return -1; // not a single full match
}

当然，您可以使用一些 Rust 特性来缩短代码(并避免上面的类 C 风格):

fn find2(haystack: &Vec<i32>, needle: &Vec<i32>) -> Option<usize> {
    for i in 0..haystack.len()-needle.len()+1 {
        if haystack[i..i+needle.len()] == needle[..] {
            return Some(i);
        }
    }
    None
}

或者如果你喜欢函数式风格:

fn find3(haystack: &Vec<i32>, needle: &Vec<i32>) -> Option<usize> {
    (0..haystack.len()-needle.len()+1)
        .filter(|&i| haystack[i..i+needle.len()] == needle[..]).next()
}

如果您了解朴素算法及其朴素实现，则可以转向更快的算法。