TY - JOUR

T1 - Tight bounds on the complexity of the Boyer-Moore string matching algorithm

AU - Cole, Richard

PY - 1994

Y1 - 1994

N2 - The problem of finding all occurrences of a pattern of length m in a text of length n is considered. It is shown that the Boyer-Moore string matching algorithm performs roughly 3n comparisons and that this bound is tight up to O(n/m); more precisely, an upper bound of 3n-3(n-m+1)/(m+2) comparisons is shown, as is a lower bound of 3n(1-o(1)) comparisons, as n/m→∞ and m→∞. While the upper bound is somewhat involved, its main elements provide a simple proof of a 4n upper bound for the same algorithm.

AB - The problem of finding all occurrences of a pattern of length m in a text of length n is considered. It is shown that the Boyer-Moore string matching algorithm performs roughly 3n comparisons and that this bound is tight up to O(n/m); more precisely, an upper bound of 3n-3(n-m+1)/(m+2) comparisons is shown, as is a lower bound of 3n(1-o(1)) comparisons, as n/m→∞ and m→∞. While the upper bound is somewhat involved, its main elements provide a simple proof of a 4n upper bound for the same algorithm.

UR - http://www.scopus.com/inward/record.url?scp=0028516714&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028516714&partnerID=8YFLogxK

U2 - 10.1137/S0097539791195543

DO - 10.1137/S0097539791195543

M3 - Article

AN - SCOPUS:0028516714

SN - 0097-5397

VL - 23

SP - 1075

EP - 1091

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -