algorithm - 后缀树：最长重复子串实现

Question

我已经实现了一个未压缩的后缀树。我想知道如何解决在字符串中查找最长重复子字符串的问题。我知道我们必须找到有两个孩子的最深的内部节点，但是如何编码。另外，我们如何知道最长的重复子串是什么。我对 JAVA 中的代码很感兴趣。请给出java实现。作为参考，我的 TrieNode 看起来像

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

score 2 · Accepted Answer

2

于 2010-12-18T19:02:02.140 回答

score 1 · Accepted Answer

如果您存储字符串字节的结尾，它只是具有 2 个子节点的最深节点。

要找到最长的子字符串，您需要进行深度优先搜索，保持对具有 2 个或更多子节点的最深节点及其深度的引用。使用递归函数最容易做到这一点。

score 0 · Accepted Answer

要找到最深的节点，也可以做 BFS 并选择具有最高级别的节点。我认为具有最高级别的节点也是最深的节点。然后您可以检查它是否有 2 个孩子。否则更高。不确定这是否可行。有什么意见吗？

3 回答 3