Module bio::pattern_matching::kmp

Algorithm of Knuth Morris and Pratt. Constructs an automaton recognizing the pattern, and scans linearly over a text of length n. Complexity: O(n). The transition function delta is simulated via the lps-function, that assigns to each position q in the pattern the longest prefix of the pattern that is suffix of pattern[..q+1]. Then, in the NFA for the pattern, active states after reading position q are {q, lps(q), lps(lps(q)), ... 0}.

Example

use bio::pattern_matching::kmp::KMP;
let text = b"aaaaabbabbbbbbbabbab";
let pattern = b"abbab";
let kmp = KMP::new(pattern);
let occ: Vec<usize> = kmp.find_all(text).collect();
assert_eq!(occ, [4, 15]);

Structs

KMP	KMP algorithm.
Matches	Iterator over start positions of matches.