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