3 ms·
BM 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
by IsTom 12y ago
BM 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