Construindo matriz de sufixos a partir da árvore de sufixos.Visita ordenada quando o nó tem mais de dois filhos

Question

Das notas:

Não é difícil observar que a matriz de sufixos $ exttt{SA}$ do texto $ exttt{T}$ pode ser obtido de sua árvore de sufixos$ exttt{ST}$ realizando uma visita ordenada:Cada vez que uma folha é encontrada, o índice de sufixo armazenado nesta folha é escrito na matriz de sufixo $ exttt{SA}$;Cada vez que um nó interno u é encontrado, seu valor associado é gravado na matriz$ exttt{lcp}$.

Como você faz a visita inorder quando um nó tem mais de dois filhos?

Digamos que você visite o filho mais à esquerda, depois o nó e depois o outro filho mais à esquerda.Então você visita novamente o nó?

SA em uma matriz de ponteiros para sufixos, ordenados lexicograficamente.

LCP contém o prefixo comum mais longo entre dois sufixos consecutivos $ ext{suff}_{SA[i]} ext{ e } ext{suff}_{SA[i+1]}$.

O \$ representa um caractere menor que qualquer outro caractere.

O valor associado a cada nó é o comprimento do prefixo escrito até agora.

As folhas representam índices de sufixos.Se T = banana\$, a folha 3 representa nana\$ (T[3,7])

Na imagem há o que deveria ser uma árvore de sufixos, mas acho que há um erro, pois as bordas devem ser classificadas de acordo com seu rótulo e a folha 7 com a borda rotulada como "\$" deve ser a folha e a borda mais à esquerda.

Ao simular o algoritmo, primeiro você visita o nó 7 (usando a versão fixa da árvore), depois a raiz, então você tem

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

Então digamos que você continue com uma visita indevida sua. Ao voltar para a raiz, você insere o valor 0 novamente no lcp?Ou você faz isso apenas na primeira vez que visita a raiz?

Answer 1

Se um nó tiver $l$ crianças, com $l \geq 2$ durante a visita inorder você tem que tratar o primeiro $1-1$ filhos como nós esquerdos, e você deve visitar o pai múltiplo ($1-1$) vezes, escrevendo várias vezes o comprimento do prefixo escrito dentro da matriz lcp.

Isso, aplicado à árvore da imagem, resultaria no correto:

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

lembrando que a borda marcada como "$" com a folha 7 deve ser a mais à esquerda.