Function kmp::kmp_find

pub fn kmp_find<N, H>(needle: &[N], haystack: &[H]) -> Option<usize> where
    N: PartialEq,
    H: PartialEq<N>, 

Finds a needle in a haystack using the Knuth–Morris–Pratt algorithm.

Returns None if the needle could not be found.

Note: This function generates a longest suffix-prefix table prior to searching. If multiple haystacks are to be searched using the same needle, consider first manually generating said table using kmp_table and then searching each haystack using kmp_find_with_lsp_table.

Examples

use kmp::kmp_find;

assert_eq!(kmp_find(&['y'], &['h', 'a', 'y', 's', 't', 'a', 'c', 'k']), Some(2));
assert_eq!(kmp_find(&[1, 2, 1], &[1, 2, 1, 2, 1]), Some(0));
assert_eq!(kmp_find(&[true, false, true], &[true, false]), None);

// because the needle and haystack only rely on being `PartialEq`, they can have different types
// hence rustc can not infer the type of `needle` and we have to define it
let empty_needle: &[&str; 0] = &[];
assert_eq!(kmp_find(empty_needle, &["some", "words"]), Some(0));