10 ms·
KMP starts with the first character of the pattern (or substring/needle) and then jumps forward by the length of the mismatch. A related algorithm is Boyer-Moor
by mavam 12y ago
KMP starts with the first character of the pattern (or substring/needle) and then jumps forward by the length of the mismatch. A related algorithm is Boyer-Moore (BM)(http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algor...), which operates the other way round: it begins with the last character of the pattern and then compares backwards until the full pattern matches. The advantage of BM is that it allows for bigger jumps.
It seems that KMP works well for small alphabets (e.g., DNA), whereas BM shines for larger alphabets (e.g., plain English).
- yxhuvud 12y agoOne difference is that BM is O(m*n) while KMP is O(n + m). Depending on how the input string looks like, this can matter - especially in small alphabets where the likelihood of pattern repeating themselves are bigger.
- IsTom 12y agoBM is too provably O(n + m) (and without dependence on alphabet size unlike KMP) if you apply two heurestics that I don't really remember. For some reason it's not mentioned on wikipedia.
- jasode 12y agoTurbo BM? http://www-igm.univ-mlv.fr/~lecroq/string/node15.html http://www-igm.univ-mlv.fr/~lecroq/string/node15.html