CODEWITHSUNDEEP
stringalgorithmdata-structurestreesuffix-tree
QuickDzen
QuickDzen

Reputation: 277

Find longest substring in two words with suffix tree

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?

Upvotes: 1

Views: 283

Answers (1)

Photon
Photon

Reputation: 2777

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)

Upvotes: 1

Related Questions