The Boyer–Moore algorithm searches for occurrences of pattern P in text T by performing explicit character comparisons at different alignments. Instead of a brute-force search of all alignments (of which there are n - m + 1), Boyer–Moore uses information gained by preprocessing P to skip as many alignments as possible. More...
#include <cassert>#include <climits>#include <cstring>#include <iostream>#include <string>#include <vector>
The Boyer–Moore algorithm searches for occurrences of pattern P in text T by performing explicit character comparisons at different alignments. Instead of a brute-force search of all alignments (of which there are n - m + 1), Boyer–Moore uses information gained by preprocessing P to skip as many alignments as possible.
The key insight in this algorithm is that if the end of the pattern is compared to the text, then jumps along the text can be made rather than checking every character of the text. The reason that this works is that in lining up the pattern against the text, the last character of the pattern is compared to the character in the text.
If the characters do not match, there is no need to continue searching backwards along the text. This leaves us with two cases.
Case 1: If the character in the text does not match any of the characters in the pattern, then the next character in the text to check is located m characters farther along the text, where m is the length of the pattern.
Case 2: If the character in the text is in the pattern, then a partial shift of the pattern along the text is done to line up along the matching character and the process is repeated.
There are two shift rules:
[The bad character rule] (https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#The_bad_character_rule)
[The good suffix rule] (https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#The_good_suffix_rule)
The shift rules are implemented as constant-time table lookups, using tables generated during the preprocessing of P.
Definition in file boyer_moore.cpp.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4