[Haskell-cafe] Knuth Morris Pratt for Lazy Bytestrings implementation

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Tue Jul 31 21:17:02 EDT 2007

On Wed, 2007-08-01 at 01:51 +0100, Tim Docker wrote:
> Now I wonder what that 7MB file might be? :-)
> We (team TNT) implemented KMP over lazy bytestrings as part of our icfp
> 2007 contest entry. As I remember, for the DNA evaluator it gave modest
> speed improvements over more naïve searching. Our implementation was based
> upon this blog post:
>     http://twan.home.fmf.nl/blog/

If anyone can come up with a fast search implementation for strict
and/or lazy ByteStrings I'll include it in the bytestring package. The
current Data.ByteString search uses a rather under-optimised KMP
implementation. I say under-optimised as I think it typically gets
beaten by a naive search.


More information about the Haskell-Cafe mailing list