Don't ask to ask, just ask | |
PerlMonks |
Re^4: Challenge: Fast Common Substrings (O(n)?)by lima1 (Curate) |
on Apr 04, 2007 at 22:12 UTC ( [id://608380]=note: print w/replies, xml ) | Need Help?? |
The naive algorithm requires O(N*N). The Ukkonen algorithm needs only O(N). If you want to understand it - it is not trivial - I recommend Gusfields book (Algorithms on Strings,...).
In Section
Seekers of Perl Wisdom
|
|