如何查找两个句子的最长公共子串？求解suffix tree后续实现步骤

你的思路方向完全正确，用拼接字符串+后缀树的方法确实能高效解决最长公共子串问题，后续推进的具体步骤如下：

• 第一步：规范拼接字符串
  把两个原序列用两个互不相同且原序列中不存在的特殊字符分隔，比如拼接成 seq1$seq2#（$和#必须是两个句子里都没出现过的字符）。这么做是为了避免后缀树中出现跨原序列的错误匹配，确保每个后缀的来源可区分。

• 第二步：构建后缀树并标记后缀来源
  构建拼接后字符串的后缀树时，给每个后缀打上来源标记：来自seq1的后缀标记为0，来自seq2的标记为1。每个节点需要记录它所覆盖的所有后缀的标记集合——如果一个节点的标记集合同时包含0和1，说明这个节点对应的子串在两个原序列中都出现过。

• 第三步：筛选最长公共子串节点
  遍历后缀树的所有节点，找出所有标记集合同时包含0和1的节点，然后在这些节点中找到从根节点到该节点的路径长度最长的那个。这条路径上的所有字符连接起来，就是两个原序列的最长公共子串。

以你给出的例子来说：

sequence 1 = "there were a dozen eggs in the basket"
sentence 2 = "mike ate a dozen eggs for breakfast"
拼接后构建后缀树，会找到对应子串e a dozen eggs 的节点，该节点的标记集合同时包含0和1，且路径长度是所有符合条件节点中最长的，这就是你要找的最长公共子串。

额外补充两个注意点：

• 如果原序列中存在多个长度相同的最长公共子串，这种方法可以一次性找出所有符合条件的节点，收集它们对应的路径即可。
• 特殊字符的选择一定要谨慎，必须确保原序列中没有相同字符，否则会干扰子串的匹配判断。

内容的提问来源于stack exchange，提问作者mk6man