Subslice search

[leonardo-m]

As enhancement, I think stdlib should contain functions that search a subslice inside a given slice:

fn contains_subslice<T: PartialEq>(data: &[T], needle: &[T]) -> bool {
    data
    .windows(needle.len())
    .any(|w| w == needle)
}

fn position_subslice<T: PartialEq>(data: &[T], needle: &[T]) -> Option<usize> {
    data
    .windows(needle.len())
    .enumerate()
    .find(|&(_, w)| w == needle)
    .map(|(i, _)| i)
}

fn main() {
    println!("{}", contains_subslice(b"hello", b"ll"));
    println!("{:?}", position_subslice(b"hello", b"ll"));
}

For the common case of T:Copy items the true stdlib functions should specialize using a smarter algorithm, like:
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

(Similar functions are useful for iterators too).

[Shnatsel]

I am baffled that this is actually not in the standard library. Functions contains and find are apparently implemented for strings but not slices?

[Shnatsel]

At least there is a third-party crate based on stdlib implementation for strings: https://github.com/strake/subslice.rs

[qingyunha]

I think this is a common function that should live in the standard library of any programming language.

[hikari-no-yume]

I'm also surprised by this. &[u8] is commonly used as a byte string type, and all the reasons you'd search a &str for a substring also apply to a &[u8].

It seems that [T]::contains() is taken (it's a function that searches for a single element). [T]::contains_slice() would make sense?

[hikari-no-yume]

Though actually, bytes.windows(3).any(|window| window == b"foo") isn't that bad.

[ByteNybbler]

I've also very much desired this functionality, particularly to check if a byte slice exists within a [u8] without having to convert it to a str first.

It seems that [T]::contains() is taken (it's a function that searches for a single element). [T]::contains_slice() would make sense?

[T]::contains could probably be upgraded to take a generic impl Pattern argument, making it more analogous to str::contains while also being backward-compatible.