A Left-to-Right Preprocessing Computation for the Boyer-Moore String Matching Algorithm
T. Takaoka · The Computer Journal · 1996
The string matching algorithm is generally divided into two phases; the preprocessing phase to obtain the shift tables and the main matching process with the tables. In the off-line version, we computed the tables after the whole pattern has been input, while in the on-line version, we computed the tables as the new character of the pattern is input, that is, on the fly. The shift table for the Knuth–Morris–Pratt (KMP) is computed from left to right, and hence suitable for the on-line version. The d-table and Horspool table in the Boyer–Moore (BM) algorithm are also computed from left to right in linear time. We show in this paper that the add-table for the BM algorithm can be computed in O(m log m) expected time from left to right for a random pattern, and hence can be incorporated into an on-line version.