the boyer-moore algorithm as presented in the original paper has worst-case running time of only if the pattern does "not" appear in the text. this was first proved by knuth, morris, and pratt in 1977,