Function kmp::kmp_match

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

Matches a needle in a haystack using the Knuth–Morris–Pratt algorithm returning a vector of positions in the haystack.

For matches that overlap, only the indices corresponding to the first match are returned.

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

Examples

use kmp::kmp_match;

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

// 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_match(empty_needle, &["some", "words"]), vec![0, 1, 2]);