How to find longest common substring using trees?
- by user384706
The longest common substring problem according to wiki can be solved using a suffix tree.
From wiki:
The longest common substrings of a set of strings can be found by
building a generalised suffix tree for the strings, and then finding
the deepest internal nodes which have leaf nodes from all the strings
in the subtree below it
I don't get this.
Example: if I have:
ABCDE and XABCZ
then the suffix tree is (some branches from XABCZ omitted due to space):
The longest common substring is ABC but it is not I can not see how the description of wiki helps here.
ABC is not the deepest internal nodes with leaf nodes.
Any help to understand how this works?