pub fn bndm(pattern: &[u8], text: &[u8]) -> Vec<usize>Expand description
An implementation of the Backward Nondeterministic DAWG Matching algorithm (BNDM).
Takes a pattern, and text text.
If the given text contains the given pattern, the algorithm returns all indexes of the first letters of the found occurrences. If the pattern could not be found in the text, an empty vector is returned.
§Runtime
The worst case runtime is O(n * m), with n being the length of the text
and m being the length of the pattern.
§When to Use It
The algorithm works best if the pattern length is not larger than the bit width of a register on your system.
§How It Works
It uses the same function to generate shift masks as the Shift-And algorithm, but reverses the pattern before passing it to the mentioned function. Also, it scans the pattern in the current search window from right to left and as soon as the pattern does not match the current window determines how far the next jump (or shift of the search window) needs to be.