algorithm - 最长重复子串问题

Question

当创建字符串“ABAB”的后缀树时，我只得到 2 个节点:

ABAB 和 BAB

最长的重复子串(“AB”)应该位于“具有至少 k 个后代的最深节点”，但我的字符串不是这种情况，这里有什么问题吗？

谢谢

Answer 1

如果您正在使用某种形式的后缀树，它只有字符串 ABAB 的两个节点，那么它不能直接与您引用的算法一起使用。后缀树应该是这样的，O 代表节点，$ 用来标记字符串的结尾。

         O
        / \
       /   \
      B     AB
     /       \
    O         O
   / \       / \
  $  AB$    $  AB$
 /     \   /     \
O       O O       O

此处的关键特征(您正在使用的树中缺少该特征)是每个叶节点对应于字符串的后缀。

具有至少两个叶子后代的最深节点位于路径 AB 处(深度是从根节点到达该节点所需的子串长度，在本例中为 2)，这确实是最长的重复子串。