Rust 是否包含一种直接检查一个向量是否为“子字符串"的方法?另一个? [英] Does Rust contain a way to directly check whether or not one vector is a "substring" of another?

问题描述

您可以使用搜索模式的 contains 使用 String 执行此操作，但 Vec::contains 用于单个元素.

You can do this with a String using contains which searches for a pattern, but Vec::contains is for a single element.

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

The only way I've been able to do this is by directly implementing some kind of substring function, but I'm sort of hoping there's a built-in way.

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 中的类型的东西.

I've seen How can I find a subsequence in a &[u8] slice?, but that's specifically for u8 and I want something that applies regardless of the type in the Vec.

推荐答案

Rust 不包含在标准库中.

Rust doesn't include this in the standard library.

一般来说，这是我们可以在任意字母表上定义的子串搜索问题.根据我们可用的属性(仅可比较或可订购)决定我们可以使用哪些算法.

In general, this is the substring search problem which we can define over arbitrary alphabets. Depending on what properties we have available (only comparable, or also orderable) determines what algorithms we can use.

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

The benefit of using a substring search algorithm is that the function performs reasonably well for all inputs. The brute force search solution has a worst case that takes a time that is quadratic in the size of the input.

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

The "alphabet" of i32 values is orderable, so the Two Way algorithm (that the Rust standard library uses in str::find(&str) internally) could be adapted to implement this.

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

One algorithm which works for all equality comparable alphabets is Knuth-Morris-Pratt. It requires preprocessing the pattern we are searching for and requires space proportional to the pattern's length. It is also quite simple to implement.

我已经为 Rust @ bluss/knuth 编写了一个算法实现morris-pratt，至少在撰写本文时，还没有作为板条箱发布.

I've written an implementation of the algorithm for generic elements for Rust @ bluss/knuth-morris-pratt, which as of this writing at least, is not published as a crate.

好吧，天哪.你可能对我狠狠地狙击了我.我花了过多的时间研究为此使用不超过 T: Eq 和 不超过 恒定空间 的算法(意思是 Rust 核心兼容的).在撰写本文时，这是一个您可以使用的板条箱:galil-seiferas.

Well, christ. You might have nerd-sniped me pretty hard. I spent an inordinate amount of time researching algorithms for this that use no more than T: Eq and no more than constant space (meaning Rust core compatible). As of this writing, it's a crate you can use: galil-seiferas.

这篇关于Rust 是否包含一种直接检查一个向量是否为“子字符串"的方法?另一个?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！