On the Worst-Case Behavior of String-Searching Algorithms

Any algorithm for finding a pattern of length k in a string of length n must examine at least $n - k + 1$ of the characters of the string in the worst case. By considering the pattern 00 ⋯ 0, we prove that this is the best possible result. Therefore there do not exist pattern matching algorithms whose worst-case behavior is “sublinear” in n (that is, linear with constant less than one), in contrast with the situation for average behavior (the Boyer-Moore algorithm is known to be sublinear on the average).