Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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!

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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