# An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?

This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm looking for a good example (text,pattern) that can clearly demonstrate this case.

• Commented Mar 27, 2015 at 12:29

Well these patterns will make KMP work faster:

T=aaaaaaaaaa P=aaaa KMP will try 10 compare steps were Boyer-Moore will take 28

Another example:

T=aaaaaaaaaa P=abab KMP will try 8 compare steps where BM will try 12.

• In the first example, both algorithms will find a match immediately, at the first shift - how would they make more than 4 comparisons? Commented Jan 30, 2017 at 10:55
• That first example does not take 10 comparisons for KMP, it takes 28 for both algorithms.
– Ryan
Commented Apr 24, 2021 at 21:58

There is a paper that did a good experiment over these string matching algorithms for different patterns: "Comparison of string matching algorithms: an aid to information content security"

Also there is a study of these string matching algorithms for Japanese language: Comparison and Improvement of String Matching Algorithms For Japanese Texts

I hope these are useful to get a sense about algorithms efficiency!