Suffixbaum: Längste String Implementierung Wiederholung

Question

Ich habe einen Suffix-Baum implementiert, die nicht komprimiert wird. Ich wollte wissen, wie das Problem zu lösen von dem längsten repreating String in einem String zu finden. Ich weiß, dass wir den tiefsten inneren Knoten mit zwei Kindern finden müssen, aber wie kann Code dies sein. Auch, wie können wir wissen, was die längste Wiederholung String ist. Ich bin in den Code in JAVA interessiert. Pls geben Java-Implementierung. Als Referenz mein TrieNode sieht aus wie

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

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.

Answer 2

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

Answer 3

To find deepest node, one can also do BFS and select node which has maximum level. I think node with maximum level is also the deepest node.then you can check if it has 2 children . else go higher. not sure if this will work though. any comments pps?