[Haskell-cafe] Re: [ANN] An efficient lazy suffix tree library
haskell at list.mightyreason.com
Mon Aug 27 13:57:19 EDT 2007
Gleb Alexeyev wrote:
> Bryan O'Sullivan wrote:
>> I just posted a library named suffixtree to Hackage.
>> It implements Giegerich and Kurtz's lazy construction algorithm, with
>> a few tweaks for better performance and resource usage.
>> API docs:
>> I've tested it on multi-megabyte input strings.
> I think I found a bug:
> import qualified Data.SuffixTree as T
>> T.countRepeats "ab" (T.construct "abab")
That is almost certainly because the algorithm expects the source string to have
a unique character at its end.
The library should either make that clear or add such a character on its own.
Otherwise the "ab" suffix is a prefix of the "abab" suffix and the shorter one
gets lost. If you end in "$" then "ab$" cannot merge with "abab$" and there are
no distinct suffixes a and b for which (isPrefixOf a b) is true.
> *Data.SuffixTree> countRepeats "ab" (construct "abab")
> *Data.SuffixTree> countRepeats "ab" (construct "abab$")
More information about the Haskell-Cafe