Arbre Suffixe: La plus longue répéter la mise en œuvre substring

Question

Je l'ai mis en place un arbre suffixe, qui est non compressé. Je voulais savoir comment résoudre le problème de trouver la plus longue sous-chaîne repreating dans une chaîne. Je sais que nous devons trouver le plus profond noeud interne avec deux enfants, mais comment peut-être le code cela. Aussi, comment pouvons-nous savoir ce que la sous-chaîne la plus longue répétition est. Je suis intéressé par le code en Java. Pls donner java mise en œuvre. Pour référence, mes TrieNode ressemble

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

Il est seulement le plus profond nœud avec 2 enfants si vous stockez un octet de fin de chaîne.

Pour la plus longue que vous aurez besoin de substring faire une profondeur rel="nofollow"> première, en gardant une référence au plus profond nœud avec 2 enfants ou plus et il est la profondeur. Ceci est plus facile à faire avec une fonction récursive.

Answer 2

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

Answer 3

Pour trouver le plus profond nœud, on peut aussi faire BFS et sélectionnez le noeud qui a le niveau maximal. Je pense que le noeud avec le niveau maximal est aussi le plus profond node.then vous pouvez vérifier si elle a 2 enfants. d'autre aller plus haut. pas sûr si cela fonctionnera bien. les pps commentaires?