后缀树：最长重复子串执行 [英] Suffix Tree: Longest repeating substring implementation

问题描述

我实现了一个后缀树，这是不COM pressed。我想知道如何解决发现的最长的重preating子在一个字符串的问题。我知道，我们必须找到两个孩子最深的内部节点，但如何能C此$ C $。此外，我们怎么知道最长的重复子是什么。我感兴趣的是code在JAVA。请给Java实现。作为参考，我的TrieNode看起来像

 类TrieNode {

焦CH;
链表＆LT; TrieNode＆GT;儿童;

}
 

解决方案

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

要找到你需要做一个深度优先搜索最长的子串，保持一个参考最深的节点有2个或更多的孩子，它的深度。这是最简单的做一个递归函数。

I have implemented a suffix tree, which is not compressed. I wanted to know how to solve the problem of finding the longest repreating substring in a string. I know that we have to find the deepest internal node with two children, but how can be code this. Also, how do we know what the longest repeating substring is. I am interested in the code in JAVA. Pls give java implementation. For reference, my TrieNode looks like

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

解决方案

It's only the deepest node with 2 children if you store an end of string byte.

To find the longest substring you'll need to do a depth first search, keeping a reference to the deepest node with 2 or more children and it's depth. This is easiest to do with a recursive function.

这篇关于后缀树：最长重复子串执行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！