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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ SO stackoverflow.com/questions/12656160/… $\endgroup$– Ciro Santilli OurBigBook.comCommented Mar 27, 2015 at 12:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
-
$\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$ Commented Jan 30, 2017 at 10:55
-
$\begingroup$ That first example does not take 10 comparisons for KMP, it takes 28 for both algorithms. $\endgroup$– RyanCommented Apr 24, 2021 at 21:58
$\begingroup$
$\endgroup$
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!
