[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: gnulib's Knuth-Morris-Pratt implementation
From: |
Eric Blake |
Subject: |
Re: gnulib's Knuth-Morris-Pratt implementation |
Date: |
Sat, 5 Jan 2008 00:13:04 +0000 (UTC) |
User-agent: |
Loom/3.14 (http://gmane.org/) |
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