基于Suffix Tree的最长公共子串求解：现有算法缺陷及优化问询

问题背景 #

给定两个长度相同、字符频次完全一致的字符串X和Y，我们要找出所有极大最长公共子串——就是那些同时出现在X和Y里，而且不管往左还是往右都没法再延长的子串。比如X=abcabc、Y=bcaabc时，正确结果是bc、abc、bca，但原思路只返回了后两个，显然漏了bc。

原思路的问题出在哪？ #

原思路第三步“移除子树中存在后缀链接的节点”完全错了。后缀链接的存在不代表当前节点的子串不是极大的。拿bc来说，它对应的节点确实有后缀链接，但bc在两个字符串里都没法延长，属于合法结果，原思路却把它误删了。

修正后的O(N)算法步骤 #

1. 带标记的广义后缀树构建 #

用Ukkonen算法建X和Y的广义后缀树，给每个叶子节点标上它属于X还是Y。每个内部节点要存这几个信息：

• 对应子串的长度
• 子树里是不是同时有X和Y的叶子（记个has_both布尔值）
• 子串在X和Y里的所有起始位置集合

2. 筛选最深有效节点 #

遍历所有内部节点，挑出满足两个条件的：

• has_both为真（说明这个子串在X和Y里都有）
• 它所有直接子节点的has_both都是假（这保证它是当前分支里最深的有效节点，子串没法再往下延长）

3. 验证子串的“极大性”（核心修正） #

对每个候选节点的子串，还要检查能不能往左右延长：

• 看子串在X里的所有起始位置，对应的前一个字符，和Y里同位置子串的前一个字符是不是不一样（没法往左延）
• 再看子串在X里的所有结束位置，对应的后一个字符，和Y里同位置子串的后一个字符是不是不一样（没法往右延）

这里可以利用后缀树里记录的起始位置集合来快速验证，不用重复遍历字符串，保证O(N)复杂度。

4. 去重输出 #

因为可能存在不同节点对应同一个子串的情况（比如重复出现的子串），最后把结果去重就行。

拿X=abcabc、Y=bcaabc验证 #

1. 建完后缀树后，bc、abc、bca对应的节点都满足“最深有效节点”的条件。
2. 验证极大性：
   • bc在X里出现在1-2、4-5，在Y里出现在2-3、5-6，前后字符都没法匹配延长，符合要求。
   • abc和bca也都没法往左右延长，符合条件。
3. 最终输出三个子串，和预期一致。

时间复杂度说明 #

• 后缀树构建：O(N)，Ukkonen算法本来就是线性时间。
• 节点遍历和标记：后缀树的节点数是O(N)，所以这一步也是线性的。
• 极大性验证：借助节点记录的起始位置，每个位置最多被检查一次，整体还是O(N)。
  整个算法的时间复杂度保持O(N)，完全符合要求。

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