algorithm - 后缀树和最长重复子串问题

Question

当对字符串 'AEKEAAEKEAAEKEA$' 运行算法时，寻找至少出现 3 次的最长子串，后缀树中的所有节点都有最多 2 个分支，这怎么可能？

正确的结果应该是子串'AEKEA'。

您可以轻松地在 online suffix tree builder 中看到树

我只是按照维基百科的描述:

"The problem of finding the longest substring with at least k occurrences can be found by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least k descendants"

我在这里错过了什么？

谢谢。

Answer 1

我认为该网站不正确。当我通过我的 suffix tree 运行“AEKEAAEKEAAEKEA”时，我得到以下树。

└── (0)
    ├── (27) $
    ├── (6) A
    │   ├── (26) $
    │   ├── (16) AEKEA
    │   │   ├── (17) $
    │   │   └── (7) AEKEA$
    │   └── (18) EKEA
    │       ├── (19) $
    │       └── (8) AEKEA
    │           ├── (9) $
    │           └── (1) AEKEA$
    ├── (4) E
    │   ├── (24) A
    │   │   ├── (25) $
    │   │   └── (14) AEKEA
    │   │       ├── (15) $
    │   │       └── (5) AEKEA$
    │   └── (20) KEA
    │       ├── (21) $
    │       └── (10) AEKEA
    │           ├── (11) $
    │           └── (2) AEKEA$
    └── (22) KEA
        ├── (23) $
        └── (12) AEKEA
            ├── (13) $
            └── (3) AEKEA$

从这个分支可以看出，您找到了出现 3 次的最长子串。

└── (0)
    ├── (27) $
    ├── (6) A
    │   ├── (26) $
    │   ├── (16) AEKEA
    │   │   ├── (17) $
    │   │   └── (7) AEKEA$
    │   └── (18) EKEA
    │       ├── (19) $
    │       └── (8) AEKEA
    │           ├── (9) $
    │           └── (1) AEKEA$