Knuth Morris Pratt vs Boyer Moore : binary alphabet vs alphabet with large number of letters

Question

I am familiar with both of the algorithms: Knuth Morris Pratt and Boyer moore.

Given a string P that composed of an alphabet with a large number of letters. which of the algorithm is better to use?

Given a string P with binary alphabet (0 or 1). which of the algorithm is better to use?

Answer 1

The main advantage of Boyer-Moore over KMP is that Boyer-Moore can have sub-linear runtime. However, this occurs when there aren't many mismatch characters that are in the pattern you're looking for (as this allows the algorithm to skip farther ahead in the text). In a large alphabet mismatch characters outside the pattern are more likely, so Boyer-Moore is probably the best choice there. Keep in mind, however, that in the worst case, BM runs in ~MN, where M is the size of the pattern, and N is the size of the text, whereas KMP is guaranteed linear.

For a binary alphabet, I'd go with KMP. The mismatch character in BM will almost always be in the pattern, so you will likely be proceeding linearly through the text, in which case there is little difference between the two algorithms. However, it's much easier to hit the worst case for BM in a binary alphabet, so KMP is safer.