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

On 7/31/07, 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/

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. Justin