4 ms·
One 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 t
by yxhuvud 12y ago
One 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