Algoritmos de conversão entre VS+LCP e árvore de sufixos

O nó da árvore de sufixos deve ser implementado com um vetor com apenas os filhos existentes na árvore, ordenados em ordem alfabética, de modo que, para buscar uma palavra, em cada nó possa se fazer uma busca binária para encontrar o filho correspondente à letra (ou deduzir que tal filho não existe).

Interface a ser implementada:

  PARTE 1:
  
  VS-AS(SA, LCP): recebe o vetor de sufixos SA e LCP de um texto T
                  e constroi e devolve a árvore de sufixos do texto T

  Search(r, P): devolve true se P ocorre no texto T e false caso contrário;
                faz a busca na árvore de sufixos r de T. 
                
  Occurrences(r, P): devolve a lista de posição em que P aparece em T,
                     obtida usando a árvore de sufixos r de T. 

  NOccurrences(r, P): devolve o número de ocorrências de P em T,
                      obtido usando a árvore de sufixos r de T. 
  
  PrintVS-AS(SA, LCP, r): imprime o SA e o LCP usados na construção
  da árvore de sufixos r e imprime a árvore de sufixos r em posordem,
  com os índices dos rótulos de cada aresta e índice de sufixo de cada folha. 

  PARTE 2:

  AS-VS(r): recebe a árvore de sufixos r de um texto T e constrói e
            devolve o vetor de sufixos de T e o vetor LCP correspondente.

  PrintAS-VS(r, SA, LCP): imprime a árvore de sufixos r, usada na construção
  no formato usado em PrintVS-AS) e os vetores SA e LCP construídos a partir dela.

Codificação das operações:

1 <T> significa construir SA e LPC para T por força-bruta (como na T8)
                e acionar AS-VS() para obter a árvore de sufixos r de T
2 <nome de um arquivo texto> significa, para o texto T que encontra-se no arquivo discriminado,
                                        construir SA e LPC para T por força-bruta (como na T8)
                                        e acionar AS-VS() para obter a árvore de sufixos r de T.
3 <P> significa Search(r, P)
4 <P> significa Occurrences(r, P)
5 <P> significa NOccurrences(r, P)
6     significa PrintVS-AS(SA, LCP, r)
7     significa PrintAS-VS(r, SA, LCP), onde SA e LPC foram obtidos de AS-VS(r)

Exemplo de entrada para o programa de testes:

1 abracadabra
3 abra
4 bra
5 ab

Saída esperada para este teste:

True
1 8
2