Re: gnulib's Knuth-Morris-Pratt implementation

[Eric Blake]

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