On improving the worst case running time of the Boyer-Moore string matching algorithm
- 1 September 1979
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 22 (9) , 505-508
- https://doi.org/10.1145/359146.359148
Abstract
It is shown how to modify the Boyer-Moore string matching algorithm so that its worst case running time is linear even when multiple occurrences of the pattern are present in the text.Keywords
This publication has 6 references indexed in Scilit:
- A fast string searching algorithmCommunications of the ACM, 1977
- A new proof of the linearity of the Boyer-Moore string searching algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- Linear pattern matching algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- The equation $a^M=b^Nc^P$ in a free group.The Michigan Mathematical Journal, 1962