On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm 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. CACM September, 1979 Galil, Z. Computational complexity, linear time, worst case, string matching, periodicity 3.74 4.40 5.25 CA790903 DB January 14, 1980 10:27 AM 3162 4 3162 2916 5 3162 3162 5 3162 3162 5 3162 3162 5 3162