How to find longest common substring using trees?
Posted
by
user384706
on Stack Overflow
See other posts from Stack Overflow
or by user384706
Published on 2012-06-12T20:14:03Z
Indexed on
2012/06/12
22:40 UTC
Read the original article
Hit count: 245
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?
© Stack Overflow or respective owner
