Rust是否包含一种直接检查一个向量是否是另一个向量的"子串"的方法？

Question

您可以String使用contains搜索模式的方法来执行此操作,但是Vec::contains针对单个元素.

我能够做到这一点的唯一方法是直接实现某种子串函数,但我有点希望有一种内置方式.

let vec1 = vec![1, 2, 3, 4, 5];
let vec2 = vec![2, 3]; // vec2 IS a substring of vec1
let vec3 = vec![1, 5]; // vec3 is NOT a substring of vec3

fn is_subvec(mainvec: &Vec<i32>, subvec: &Vec<i32>) -> bool {
    if subvec.len() == 0 { return true; }
    if mainvec.len() == 0 { return false; }

    'outer: for i in 0..mainvec.len() {
        for j in 0..subvec.len() {
            if mainvec[i+j] != subvec[j] {
                continue 'outer;
            }
        }
        return true;
    }
    return false;
}

println!("should be true: {}", is_subvec(&vec1, &vec2));
println!("should be false: {}", is_subvec(&vec1, &vec3));

我已经看过如何在&[u8]切片中找到子序列？,但这是专门为u8我而且我想要一些适用的东西,无论其类型如何Vec.

Answer 1

据我所知，标准库中没有函数或方法来检查一个切片是否是另一个切片的子切片。

我们可以将您的算法概括并简化为（游乐场）：

fn is_sub<T: PartialEq>(mut haystack: &[T], needle: &[T]) -> bool {
    if needle.len() == 0 { return true; }
    while !haystack.is_empty() {
        if haystack.starts_with(needle) { return true; }
        haystack = &haystack[1..];
    }
    false
}

fn main() {
    let vec1 = vec![1, 2, 3, 4, 5];
    let vec2 = vec![2, 3]; // vec2 IS a substring of vec1
    let vec3 = vec![1, 5]; // vec3 is NOT a substring of vec3

    println!("should be true: {}", is_sub(&vec1, &vec2));
    println!("should be false: {}", is_sub(&vec1, &vec3));
}

逻辑是，我们检查needle切片是否是切片的前缀haystack，如果不是，我们从 中“删除”一个元素haystack。如果haystack最终结果为空，则它不是子切片。

借助函数式编程的方法，windows我们可以进一步缩短：is_sub

fn is_sub<T: PartialEq>(haystack: &[T], needle: &[T]) -> bool {
    haystack.windows(needle.len()).any(|c| c == needle)
}

值得注意的是，这些不是最快的算法，因为它们的最坏情况复杂度为O(n^2)，但它们适用于所有T: PartialEq。Knuth-Morris-Pratt等算法可用于加速这一过程，但O(n^2)由于常数因素，对于小输入可能会更好。

我们可以通过将特征与专业化结合使用来改善这种情况（这需要每晚）：

#![feature(specialization)]

pub trait HasPart {
    fn has_part(&self, rhs: &Self) -> bool;
}

impl<T: PartialEq> HasPart for [T] {
    default fn has_part(&self, rhs: &Self) -> bool {
        self.windows(rhs.len()).any(|curr| curr == rhs)
    }
}

impl HasPart for [u8] {
    fn has_part(&self, rhs: &Self) -> bool {
        unimplemented!() // use Knuth-Morris-Pratt
    }
}

fn main() {
    let vec1 = vec![1, 2, 3, 4, 5];
    let vec2 = vec![2, 3]; // vec2 IS a substring of vec1
    let vec3 = vec![1, 5]; // vec3 is NOT a substring of vec3

    println!("should be true: {}", vec1.has_part(&vec2));
    println!("should be false: {}", vec1.has_part(&vec3));
}

Answer 2

Rust在标准库中不包含此内容.

通常,这是我们可以在任意字母表上定义的子字符串搜索问题.根据我们可用的属性(仅可比较或可订购)确定我们可以使用的算法.

使用子字符串搜索算法的好处是该函数对所有输入都表现得相当好.蛮力搜索解决方案的最坏情况是需要一个输入大小为二次的时间.

i32值的"字母" 是可订购的,因此可以调整双向算法(Rust标准库在str::find(&str)内部使用)来实现这一点.

Knuth-Morris-Pratt是一种适用于所有可比较字母表的算法.它需要预处理我们正在搜索的模式,并且需要与模式长度成比例的空间.实施起来也很简单.

我已经为Rust @ bluss/knuth-morris-pratt写了一个通用元素算法的实现,至少在撰写本文时,它并没有作为箱子出版.

好吧,基督.你可能有书呆子 - 非常努力地狙击我.我花费了大量的时间研究算法,使用不超过T: Eq 和不超过恒定的空间(意味着Rust核心兼容).在撰写本文时,它是一个可以使用的箱子:galil-seiferas.