仅用Suffix-Tree的Shortest non-repeatable Substring算法设计

核心逻辑前提 #

后缀树是对文本所有后缀建立的压缩树结构，每个节点对应一段唯一的公共子串：

• 每个叶节点对应原文本中一个后缀的起始位置
• 节点对应子串的出现次数，等于该节点子树包含的叶节点总数（所有经过该节点的后缀，都是以这个节点对应子串为开头的）
  我们要找的目标，是所有满足“出现次数为1”的子串中长度最短的那一个。

算法实现步骤 #

1. 构建带属性的后缀树 #

基于Ukkonen算法在O(n)线性时间内构建原文本的后缀树，为每个节点维护两个核心属性：

• path_length：从根节点到当前节点累计的路径长度，即当前节点对应子串的字符长度
• occur_count：当前节点对应子串的全局出现次数

属性计算通过一次后序遍历完成：

• 所有叶节点的occur_count固定为1
• 所有内部节点的occur_count等于其所有直接子节点的occur_count之和
  整个遍历过程为线性时间复杂度，无额外指数级开销。

2. 广度优先遍历定位最短候选 #

因为我们要找长度最小的子串，采用BFS从根节点开始按路径长度逐层向下遍历（天然优先访问短路径，不需要全树遍历），遍历规则如下：

• 对当前访问的节点u，逐一检查它的所有出边
• 若某条出边指向的子节点v满足occur_count == 1：
  • 说明这条边覆盖的后缀没有任何其他分支共享，从u出发沿这条边取任意长度的子串，出现次数都为1
  • 最短候选的长度为 u.path_length + 1（因为u本身的出现次数必然>=2，否则u会被更早判定为候选）
  • 最终结果为：u对应的子串，拼接这条边的第一个字符，直接返回。因为BFS是按长度从小到大遍历的，第一个命中的候选就是全局最短的
• 若子节点v的occur_count > 1，将v加入BFS待访问队列，继续向下遍历

参考用例验证 #

1. 示例1：文本AATGCCTA
   • BFS第一层访问根节点，检查出边：A对应子节点出现次数3、T对应子节点出现次数2、G对应子节点出现次数1
   • 触发判定规则，候选长度为0+1=1，返回结果G，和预期一致
2. 示例2：文本AAAAGGGG
   • BFS第一层访问根节点，出边对应A子节点（出现次数4）、G子节点（出现次数4），均入队
   • BFS第二层访问A子节点（path长度1），检查出边：A开头的子节点出现次数3、G开头的子节点出现次数1
   • 触发判定规则，候选长度为1+1=2，返回结果AG，和预期一致

复杂度说明 #

整个算法基于线性时间的后缀树构建、线性后序遍历计算频次、早停式BFS遍历，整体时间复杂度为O(n)，空间复杂度为O(n)，完全适配长文本的检索场景。

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