Creazione di un array di suffissi dall'albero dei suffissi.Visita in ordine quando il nodo ha più di due figli

Question

Dalle note:

Non è difficile osservare che l'array dei suffissi $ exttt{SA}$ del testo $ exttt{T}$ può essere ottenuto dal suo albero dei suffissi$ exttt{ST}$ eseguendo una visita in ordine:Ogni volta che si incontra una foglia, l'indice suffisso memorizzato in questa foglia viene scritto nell'array suffisso $ exttt{SA}$;Ogni volta che si incontra un nodo interno U, il suo valore associato viene scritto nell'array$ exttt{lcp}$.

Come si esegue la visita in ordine quando un nodo ha più di due figli?

Diciamo che visiti il ​​figlio più a sinistra, poi il nodo, quindi l'altro figlio più a sinistra.Quindi visiti di nuovo il nodo?

SA in una serie di puntatori ai suffissi, ordinati lessicograficamente.

lcp contiene il prefisso comune più lungo tra due suffissi consecutivi $ ext{suff}_{SA[i]} ext{ e } ext{suff}_{SA[i+1]}$.

\$ rappresenta un carattere più piccolo di ogni altro carattere.

Il valore associato a ciascun nodo è la lunghezza del prefisso digitato finora.

Le foglie rappresentano gli indici dei suffissi.Se T = banana\$, la foglia 3 rappresenta nana\$ (T[3,7])

Nell'immagine c'è quello che dovrebbe essere un albero dei suffissi, ma penso che ci sia un errore poiché i bordi dovrebbero essere ordinati in base alla loro etichetta e la foglia 7 con il bordo etichettato "\$" dovrebbe essere la foglia e il bordo più a sinistra.

Quando si simula l'algoritmo, prima visiti il ​​nodo 7 (usando la versione fissa dell'albero), poi la radice, quindi hai

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

Allora diciamo che continui con una tua visita in ordine. Quando torni alla radice, inserisci nuovamente il valore 0 in lcp?Oppure lo fai solo la prima volta che hai visitato la radice?

Answer 1

Se un nodo ha $l$ bambini, con $l \geq 2$ durante la visita in ordine bisogna trattare il primo $l-1$ figli come nodi di sinistra e devi visitare il multiplo genitore ($l-1$) volte, scrivendo più volte la lunghezza del prefisso scritto all'interno dell'array lcp.

Questo, applicato all'albero nell'immagine, produrrebbe il risultato corretto:

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

tenendo presente che il bordo etichettato "$" con la foglia 7 dovrebbe essere quello più a sinistra.