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

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

class TrieNode{ 

char ch; 
LinkedList<TrieNode> child; 

}

来源

2010-12-18 TimeToCodeTheRoad

http://stackoverflow.com/a/24705760/69663给出了一种方法来过滤掉重叠（虽然它也过滤了一些字符串的全部等于字母） – unhammer 2016-12-26 08:36:28

的算法，这是只有2个孩子最深的节点，如果你存储字节的字符串的结束。

要找到最长的子字符串，你需要做一个depth first search，保留一个对具有2个或更多子元素的最深节点的引用，并且它是深度。这是递归函数最容易做到的。

来源

2010-12-18 19:11:46

正确，但这会给答案重叠允许。我的意思是字符串“香蕉”，答案是“ana”。我想重叠不允许。所以答案应该是“an”或“na” – TimeToCodeTheRoad 2010-12-18 21:16:27

好吧，我不确定你的意思是重叠，也许不止一次使用1个字母？无论如何，如果您不想包含特定的字符串，那么当您进行深度优先搜索时，只需排除不符合您的标准的节点。 – 2010-12-19 08:48:32

你可以通过在https://daniel-hug.github.io/longest-repeated-substring/中输入“aaa”来看到重叠的问题 - 它声称“aa”是一个重复的子字符串，因为在树中[ （ “$”，叶），（ “A”，[（ “$”，叶），（ “A”，[（ “$”，叶），（ “A $”，叶）]）]）]' ，具有两个叶子后代的最深节点具有前缀“aa”的路径。 – unhammer 2016-12-17 10:24:19

Aho- Corasick http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

来源

2010-12-18 19:02:02

要找到最深的节点，还可以做BFS和选择具有最高级别的节点。我认为具有最高级别的节点也是最深的节点，然后可以检查它是否有2个孩子。否则会更高。不知道这是否会工作。任何意见pps？

来源

2010-12-18 19:56:37 Programmer

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

回答

相关问题