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

Justin Bailey jgbailey at gmail.com
Wed Aug 1 11:39:29 EDT 2007

On 7/31/07, Tim Docker <twd_gg at dockerz.net> 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/
> Tim

What prompted this was we adapted Oleg's KMP module for PackedStrings
to lazy bytestrings, and it was too slow. I am actually interested in
implementing KMP for Data.Sequence, but wanted to get bytestrings out
of the way first.


More information about the Haskell-Cafe mailing list