当对字符串 '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"
我在这里错过了什么?
谢谢。
最佳答案
我认为该网站不正确。当我通过我的 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$
关于algorithm - 后缀树和最长重复子串问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10948847/