string - 用后缀树查找两个单词中最长的子串

Question

我需要解决问题 - 用后缀树在两个单词中找到最长的子字符串。我为第一个和第二个单词建立了后缀，但是如何在两个单词中找到最长的子字符串？你能建议一个可能的算法来解决这个问题吗？

标签： stringalgorithmdata-structurestreesuffix-tree

Answer 1

诀窍是对两个单词使用单个后缀树：

1. 首先使用一些非字符串字符，如$or#或某些东西（不能是任何字符串的一部分）来连接字符串

   即字符串abra并abracadabra加入abra$abracadabra#

2. 然后从中构建后缀树。

3. $现在从以爬上结尾的叶子开始，并将节点标记为 word1 的一部分

4. 对以 结尾的叶子执行相同的#操作，将它们标记为 word2 的一部分

5. 现在我们可以DFS从根进行简单的遍历，因为最长的子字符串将是根的一些路径（仅检查同时属于两个单词的节点）

复杂性- O(a+b)（后缀树构建（如果构建快速方式）+ O(a+b)（dfs）=O(a+b)