Perl: the Markov chain saw | |
PerlMonks |
Re^3: Challenge: Fast Common Substrings (O(n)?)by tye (Sage) |
on Apr 04, 2007 at 21:53 UTC ( [id://608378]=note: print w/replies, xml ) | Need Help?? |
The page you link to mentions being able to build them in O(n) but then only really describes how to go from a suffix tree for string $x to one for string $x.$c (1==length$c) in O(length $x). Using that algorithm would require O(N*N) to build the suffix tree for a string of length N. So I'm not sure I believe the O(N) claim for building the whole suffix tree based on that page. - tye
In Section
Seekers of Perl Wisdom
|
|