Sufijo árbol: Mayor repetir la aplicación subcadena

Question

He implementado un árbol de sufijos, que no se comprime. Yo quería saber cómo resolver el problema de encontrar la subcadena más larga repreating en una cadena. Sé que tenemos que encontrar el nodo interno más profundo y con dos hijos, pero ¿cómo puede ser el código de este. Además, ¿cómo sabemos lo que la subcadena más larga es la repetición. Estoy interesado en el código en Java. Pls dan java aplicación. Como referencia, mis TrieNode se parece a

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

Es sólo el nodo más profundo con 2 niños si almacena un byte final de la cadena.

Para encontrar la subcadena más larga que necesita para hacer una profundidad primera búsqueda , mantener una referencia al nodo más profundo con 2 o más hijos y es la profundidad. Esto es más fácil de hacer con una función recursiva.

Answer 2

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

Answer 3

Para encontrar el nodo más profundo, se puede también hacer BFS y seleccione el nodo que tiene el máximo nivel. Creo nodo con el nivel máximo es también el más profundo node.then se puede comprobar si tiene 2 hijos. cosa ir más alto. no estoy seguro si esto funcionará sin embargo. cualquier comentario pps?