10
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the first example, both algorithms will find a match immediately, at the first shift - how would they make more than 4 comparisons? $\endgroup$ – BartoszKP Jan 30 '17 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.