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

Question

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.

Answer 1

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!

Answer 2

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.