QOTW 14 solves a slightly different problem, the longest
repeated substring in a single string which is somewhat
related
Here is my suffix trees based QOTW entry updated for LCS. In a sense this is the
fastest type of algorithm possible, since it's guaranteed linear in both time and space relative to the combined string length (add one termination character to each string, and actually there is also O(number_of_strings) due to the way I currently mark the strings, though that can be improved upon)
Unfortunately the needed complex datastructures make it use
so much memory and need so much setup that many of the clever
solutions in QOTW 14 can be converted to effectively faster solutions.
| [reply] [Watch: Dir/Any] [d/l] |
Hi,
I was referred to your node above from my earlier
request about Generalized Suffix Tree.
Since I am very interested to the use of it for bioinformatics purpose.
I just want to clarify:
- Does you implementation
above covers the "generalized" suffix tree?
Or is it the same with S.Yona's module?
- If so, do you have a CPAN module for it?
- Otherwise, I would really appreciate
if you can kindly point me where can I find the actual Perl implementation for it, if you happen to know one.
Thanks so much beforehand.
Hope to hear from you again.
| [reply] [Watch: Dir/Any] |
| [reply] [Watch: Dir/Any] |
In fact, my unsubmitted entry to QOTW #14 is where my repeated_substring() routine came from
| [reply] [Watch: Dir/Any] |