snippetMinor
An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?
Viewed 0 times
morrisexamplewherethanprattalgorithmfasterknuthboyermoore
Problem
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.
I'm looking for a good example (text,pattern) that can clearly demonstrate this case.
Solution
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.
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.
Context
StackExchange Computer Science Q#9635, answer score: 4
Revisions (0)
No revisions yet.