[−][src]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]);