Some Problem Solved by Suffix Tree

Problem 1: Find the longest common substring among k strings.

Solution: If we use DP, it takes O(n1*n2*...nk). With suffix tree, it takes O(n1+n2+...nk). Basically, we build the suffix tree for n1 first, then add n2 to this tree, then n3... All the strings share the same generalized suffix tree. We need to track if each node (path) is shared by all the string or not. When the building is done, the longest common substring will be found.


Problem 2: Find the longest repeated substring in a string.

Solution: First, build the suffix tree for this string. Then find the deepest internal node, from the root to that node is the substring we are looking for. The "deepest" is decided by the number of characters.