Finding index of slice idiomatically (needle in the haystack)

December 11, 2022

Javascript provides
"abcde".indexOf("de") === 3.

I’d like to do the same thing for a &[T] where T implements PartialEq.

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))
}

I could write this function myself but it seems like something the stdlib would offer, and I have not been able to find it. How do I accomplish this efficiently using the stdlib (not nightly).

>Solution :

You can use slice.windows(n) to get an iterator of all subslices of length n. You can combine that with iterator.position() to find the first subslice that is equal to needle:

fn search_haystack<T: PartialEq>(needle: &[T], haystack: &[T]) -> Option<usize> {
    if needle.is_empty() {
        // special case: `haystack.windows(0)` will panic, so this case
        // needs to be handled separately in whatever way you feel is
        // appropriate
        return Some(0);
    }

    haystack.windows(needle.len()).position(|subslice| subslice == needle)
}