in reply to
Re: Challenge: Fast Common Substrings
in thread Challenge: Fast Common Substrings
++ Wow, thank you for introducing me to suffix trees. What an interesting concept, and how refreshing to see a lineartime algorithm for constructing such a creature.
I see you've used the javascript applet at this page, which others may want to check out.
However, I'd like to slightly revise the algorithm you outlined. Consider the following example:
string = ababc%bc$
 (3:abc%bc$)leaf
(1:ab)
 (5:c%bc$)leaf
tree:
 (3:abc%bc$)leaf
(2:b)
  (6:%bc$)leaf
 (5:c)
  (9:$)leaf

 (6:%bc$)leaf
(5:c)
 (9:$)leaf

(6:%bc$)leaf

(9:$)leaf
"ab" appears twice in the first string, and so it gives a node with two leaves. The actual condition you should check is whether a node has one leaf containing the % separator and another leaf without the % symbol.