Eric Blake <ebb9 <at> byu.net> writes: > http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 > > It has the nice property of O(1) preprocessing and O(N) comparisons (strictly > bounded at 2N-M in the worst case),
correction - O(M) preprocessing, O(1) space, and O(N) comparisons. It's not as fast as turbo-Boyer-Moore on non-repetitive long needles [O(n) vs O (n/m)], but your earlier argument that since we don't take the preprocessing hit until after 5*N comparisons in the naive approach, this shouldn't matter. -- Eric Blake
