algorithm - 最长重复子串问题

当创建字符串“abab”的后缀树时，我只得到2个节点：
abab和bab
最长的repeatead子串（“ab”）应该由“具有至少k个子串的最深节点”定位，但我的字符串不是这样的，这里有什么问题？
谢谢

最佳答案

如果您使用某种形式的后缀树，其中只有两个节点用于字符串abab，那么它将无法直接使用您引用的算法。后缀树应该是这样的，O表示节点，$用于标记字符串的结尾。

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

这里的关键特性（以及您正在使用的树中缺少的特性）是每个叶节点对应于字符串的后缀。
具有至少两个叶后代的最深节点位于路径ab（深度是从根到达该节点所需的子串长度，在本例中为2），并且这确实是最长的重复子串。