Skip Navigation

The Computer Journal 1996 39(5):413-416; doi:10.1093/comjnl/39.5.413
© 1996 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Takaoka, T.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

A Left-to-Right Preprocessing Computation for the Boyer–Moore String Matching Algorithm

T. Takaoka *

Department of Computer Science, Ibaraki University, Hitachi, Ibaraki 316, Japan

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.

Received October 18, 1995. revised June 27, 1996.

* Department of Computer Science, Ibaraki University, Hitachi, Ibaraki 316, Japan Email: takaoka{at}cis.ibaraki.ac.jp


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.