[Haskell-cafe] Re: Memoizing longest-common-subsequence

[Jared Updike]

> and also ended up with an STArray based implementation. I can send the
> code if you're interested. I have no idea how well it performs compared
> to Ian's, or the one in darcs (which uses PackedStrings).

Ian's LCS code looks like it works fine in terms of space usage, but
for large input (lengrh as == 40000, length bs == 50000) it seems to
be way too slow in terms of time complexity (GNU sdiff executes on
this same data in a few seconds, the Hunt-Szymanski LCS algorithm
didn't terminate, even after like 10 minutes).

If it's not too much trouble, could you send Myers STArray based code?

Thanks,
  Jared.
-- 
http://www.updike.org/~jared/
reverse ")-:"