后缀树：最长的重复子字符串实现

Question

我已经实现了一个没有压缩的后缀树。我想知道如何解决在字符串中找到最长的重复底带的问题。我知道我们必须与两个孩子一起找到最深的内部节点，但是怎么能做到这一点。另外，我们如何知道最长的重复子弦是什么。我对Java中的代码感兴趣。请提供Java实施。作为参考，我的trienode看起来像

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

如果您存储字符串字节的末端，这只是最深的节点，有2个孩子。

要找到最长的子字符串，您需要做一个 深度搜索, ，请参考有2个或更多孩子的最深节点，这是深度。这是递归功能最简单的。

Answer 2

Aho-Corasick的算法 http://en.wikipedia.org/wiki/aho%E2%80%93corasick_string_matching_algorithm

Answer 3

要找到最深的节点，也可以进行BFS并选择具有最大级别的节点。我认为最大级别的节点也是最深的节点。然后，您可以检查它是否有2个孩子。否则走得更高。不确定这是否会起作用。有没有评论pps？