Gamme de suffixe de bâtiment de Suffix Tree.Visite d'inondation lorsque le nœud a plus de deux enfants

Question

des notes:

Il n'est pas difficile d'observer que le dispositif de suffixe $ \ TEXTTT {SA} $ de Le texte $ \ texttt {t} $ peut être obtenu à partir de son arbre suffixe $ \ textttt {st} $ en effectuant une visite en ordre: chaque fois qu'une feuille est rencontré, le suffixe-index stocké dans cette feuille est écrit dans le suffixe array $ \ texttt {SA} $ ; Chaque fois qu'un nœud interne est u est rencontré, sa valeur associée est écrite dans le tableau $ \ textttt {lcp} $ .

Comment faites-vous la visite de l'utilisateur lorsqu'un nœud a plus de deux enfants?

Disons que vous visitez l'enfant le plus à gauche, puis le nœud, puis l'autre enfant le plus à gauche. Ensuite, rendez-vous à nouveau le nœud?

SA dans un tableau de pointeur aux suffixes, commandé lexicographiquement.

lcp contient le préfixe commun le plus long entre deux suffixes consécutifs $ \ text {suff} _ {SA [i]} \ texte {et \ text. {suff} _ {SA [i + 1]} $ .

Le \ $ représente un caractère plus petit que tous les autres caractères.

La valeur associée à chaque nœud est la longueur du préfixe orthographié jusqu'à présent.

Les feuilles représentent des indices de suffixes. Si t= banane \ $, la feuille 3 représente Nana \ $ (T [3,7])

Dans l'image, il y a ce qui est censé être un arbre suffixe, mais je pense qu'il y a une erreur car les bords doivent être triés en fonction de leur étiquette et la feuille 7 avec le bord marqué "\ $" devrait être la feuille la plus à gauche et bord.

Lors de la simulation de l'algorithme, vous visitez d'abord le nœud 7 (à l'aide de la version fixe de l'arborescence), puis de la racine, de sorte que vous avez

SA = [7, ...]
lcp = [0, ...]

Alors disons que vous continuez à continuer avec une visite d'inondation de vous. Lorsque vous revenez à la racine, insérez-vous la valeur 0 à nouveau dans le LCP ? Ou faites-vous cela juste la première fois que vous avez visité la racine?

Answer 1

Si un nœud a $ l $ enfants, avec $ l \ geq 2 $ pendant l'insertionVisitez que vous devez traiter le premier $ L-1 $ enfants comme des nœuds de gauche, et vous devez visiter le parent multiple ($ L-1 $ ) fois, écrivez plusieurs fois la longueur du préfixe orthographié à l'intérieur de la matrice LCP.

Ceci, appliqué à l'arborescence de l'image, céderait le bon:

SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

Gardant à l'esprit que le bord étiqueté "$" avec la feuille 7 doit être le plus à gauche.