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

当在字符串'AEKEAAEKEAAEKEA$'上运行算法寻找最长的子字符串并且至少有3次发生时，后缀树中的所有节点都有最多2个分支，这怎么可能？后缀树和最长的重复子字符串问题

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

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

我只是跟着Wikipedi描述：

“至少k处发现的最长的串出现的问题可以通过第一预处理发现该树计算每个内部节点的叶子后代数，然后找到具有至少k个后代的最深节点“

我在这里错过了什么？

谢谢。

来源

2012-06-08 kukit

我不认为这个网站是正确的。当我通过我的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$

来源

2012-06-08 13:05:31 Justin

谢谢你，但我有点困惑，在你的树，还有每个节点的分支的最大数量为2 – kukit

节点0有4个分公司和节点6有3个分支。 – Justin

是的，对不起，你是对的，但是节点0意味着“”，节点6意味着“A”并且没有节点意味着“AEKEA”并且有两个以上的分支 – kukit

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

回答

相关问题