Suffisso Albero: Longest ripetendo substring implementazione

Question

Ho implementato un albero suffisso, che non è compresso. Volevo sapere come risolvere il problema di trovare sottostringa repreating più lungo in una stringa. So che dobbiamo trovare il nodo interno più profondo con due figli, ma come può essere il codice presente. Inoltre, come facciamo a sapere quello che la stringa più lunga ripetizione è. Sono interessato il codice in Java. Pls dare java attuazione. Per riferimento, il mio aspetto TrieNode come

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

E 'solo il nodo più profondo con 2 bambini, se si memorizza una fine di byte di stringa.

Per trovare la più lunga sottostringa è necessario fare una profondità prima ricerca , mantenendo un riferimento al nodo più profonda con 2 o più bambini ed è di profondità. Questo è più facile a che fare con una funzione ricorsiva.

Answer 2

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

Answer 3

Per trovare più profondo del nodo, si può anche fare BFS e selezionare il nodo che ha il livello massimo. Penso nodo con il livello massimo è anche il più profondo node.then è possibile controllare se ha 2 figli. altro andare più in alto. non so se questo funzionerà però. ogni commento pps?