On improving the worst case running time of the Boyer-Moore string matching algorithm

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.

REFERENCES

• 1: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 2: Guibas, L.J., and Odlyzko, A.M. A new proof of the linearity of the Boyer-Moore string searching algorithms. Proc. 18th Ann. 1EEE Symp. Foundations ofComptr. Sci., 1977, pp. 189-195.
• 3: Knuth, D.E., Morris, Jr., J.H., and Pratt, V.B. Fast pattern matching in strings. SlAM J. Comping. 6, 2 (1977), 323-350.
• 4: Lyndon, R.C., and Schutzenberger, M.P. The equation a M = bNc P in a free group. Michigan Math. J. 9 (1962), 289-298.
• 5: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 6: Weiner, P. Linear pattern matching algorithm. Proc. 14th Ann. IEEE Symp. Switching and Automata Theory, 1973, pp. 1-11.
• 7: Yao, A.C.C. The complexity of pattern matching for a random string. Mss., Comptr. Sci. Dept., Stanford U., Stanford, Calif., 1977.

INDEX TERMS

Keywords:
computational complexity, linear time, periodicity, string matching, worst case