后缀树和最长重复子字符串问题
在字符串“aekeaekea$”上运行算法以查找至少出现3次的最长子字符串时，后缀树中的所有节点最多有2个分支，这是怎么回事？
您可以在联机后缀树生成器中轻松查看树
我只是按照维基百科的描述：
查找出现次数至少为k次的最长子字符串的问题可以通过以下方法找到：首先对树进行预处理，以计算每个内部节点的叶后代数，然后查找出现次数至少为k次的最深节点
我错过了什么？
非常感谢。
共有1个答案
我认为那个网站不对。当我在后缀树中运行'aekeaekeaekea'时，我得到以下树。
└── (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$
-
最长的重复子串问题如下： 给定一个字符串w，找到至少出现在两个位置的w的最长子串。 这个问题可以在线性时间使用后缀树解决，在线性时间使用增强的后缀数组解决。 我的问题是——对于这个问题，有没有不涉及后缀树或后缀数组的线性时间算法？我很好奇，因为后缀树和后缀数组很难编码和操作，如果有一种算法解决这个问题，而不需要这些其他结构的编码或内存开销，那就太好了。 谢谢
-
题目描述 输入一个字符串（只包含 a~z 的字符），求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。 解题思路 // java public int longestSubStringWithoutDuplication(String str) { int curLen = 0; int maxLen = 0;
-
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，
-
我知道这是一个有点老生常谈的话题，但我已经达到了从已经得到的答案中得到的帮助的极限。 这是针对Rosalind项目问题LREP的。我试图找到字符串中最长的k-peated子串，我得到了后缀树，这很好。我知道我需要用每个节点的后代叶子数来注释后缀表，然后用
-
我已经解决了寻找最长回文子字符串的问题，但这是不同的。给定一个像“ababa”这样的字符串，所有前缀的最长回文子字符串的长度如下所示- “a”：“a”（长度1) “ab”：“a”或“b”（长度1) “aba”：“aba”（长度3) “abab”：“aba”或“bab”（长度3) “亚贝巴”：“亚贝巴”（长度5) null null 我们只需要长度，而不是实际的回文。有没有更容易/更好（就运行时复杂
-
解决此问题的最佳方法（性能方面）是什么？有人建议我使用后缀树。这是最好的方法吗？