Construyendo la matriz del sufijo del árbol del sufijo.Visita enodor cuando el nodo tiene más de dos hijos.

Question

de las notas:

No es difícil observar que la matriz de sufijo $ \ texttt {sa} $ de El texto $ \ texttt {t} $ se puede obtener de su árbol de sufijo $ \ texttt {st} $ realizando una visita en orden: cada vez que una hoja es Encontrado, el índice de sufijo almacenado en esta hoja está escrito en el sufijo matriz $ \ texttt {sa} $ ; Cada vez que un nodo interno u es Encontrado, su valor asociado está escrito en la matriz. $ \ texttt {lcp} $ .

¿Cómo realiza la visita de entrada cuando un nodo tiene más de dos hijos?

Digamos que visitas al niño más a la izquierda, luego el nodo, luego el otro niño más a la izquierda. Entonces, ¿visitas de nuevo el nodo?

SA en una matriz de puntero a los sufijos, ordenados lexicográficamente.

LCP contiene el prefijo común más largo entre dos sufijos consecutivos $ \ texto {SA} _ {SA [I]} \ texto {y} \ texto {SUFF} _ {SA [I + 1]} $ .

El \ $ representa un char que es más pequeño que todos los demás char.

El valor asociado a cada nodo es la longitud del prefijo escrito hasta ahora.

Las hojas representa índices de sufijos. Si t= banana \ $, la hoja 3 representa a NANA \ $ (t [3,7])

En la imagen, se supone lo que se supone que es un árbol de sufijo, pero creo que hay un error, ya que los bordes deben ordenarse de acuerdo con su etiqueta y la hoja 7 con el borde etiquetada "\ $" debe ser la hoja más a la izquierda y borde.

Al simular el algoritmo, primero visita el nodo 7 (usando la versión fija del árbol), luego la raíz, para que tenga

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

Entonces digamos que sigues pasando con una visita de entrada de U. Cuando vuelva a la raíz, ¿inserta el valor 0 nuevamente en el LCP ? ¿O lo haces solo la primera vez que visitó la raíz?

Answer 1

Si un nodo tiene $ l $ niños, con $ l \ geq 2 $ durante elVisita Tienes que tratar el primer $ l-1 $ niños como nodos izquierdos, y tiene que visitar el padre múltiple ($ l-1 $ ) veces, escribiendo varias veces la longitud del prefijo escrito dentro de la matriz LCP.

Esto, aplicado al árbol en la imagen, daría el correcto:

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

Teniendo en cuenta que el borde etiquetado "$" con la hoja 7 debería ser la más a la izquierda.