首页 文章

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

提问于
浏览 次
1

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

正确的结果应该是子字符串' AEKEA ' .

你可以很容易地看到online suffix tree builder中的树

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

“通过首先预处理树来计算每个内部节点的叶子后代的数量，然后找到至少有k个后代的最深节点”，可以找到找到具有至少k次出现的最长子串的问题 .

我在这里错过了什么？

谢谢 .

algorithm suffix-tree

1 回答

  • 3

    我通过我的suffix tree，我得到了以下的树#II26071_ 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$
    回复于

相关问题