Find longest substring in two words with suffix tree

Question

I need to solve problem - find longest substring in two words with suffix tree. I built suffix for first and secod word, but how can I find longest substring in two words? Could you suggest a possible algorithm for solving this problem?

Answer 1

The trick is to use a single suffix tree for both words:

1. First use some non-strings character like $ or # or something (must not be part of any string) to join strings

   i.e. strings abra and abracadabra get joined to abra$abracadabra#

2. Then build suffix tree from that.

3. Now from leaves ending with $ climb up and mark nodes as part of word1

4. Do the same for leaves ending with #, marking them as part of word2

5. Now we can do simple DFS traversal from root, as longest sub-string will be some path from root (only checking nodes that are part of both words)

Complexity - O(a+b) (suffix tree building (if build fast way) + O(a+b) (dfs) = O(a+b)