Árvore de sufixos
De Wikipedia, a enciclopédia encyclopedia
Em ciência da computação, uma árvore de sufixos (também chamada árvore PAT ou, na forma anterior, árvore de posições) é uma trie comprimida, contendo todos os sufixos de um dado texto, assim como suas chaves e posições no texto como seus valores. Árvores de sufixo permitem uma implementação particularmente rápida de muitas operações importantes com strings.
A construção de tal árvore para uma string leva tempo e espaço lineares no tamanho de . Uma vez construída, muitas operações podem ser realizadas rapidamente, por exemplo, localizar uma substring em , localizar uma substring se um certo número de erros for permitido, localizar acertos para uma expressão regular etc. Árvores de sufixo também proveem uma das primeiras soluções em tempo linear para o problema da maior substring comum. Estes ganhos de velocidade vem com um custo: armazenar uma árvore de sufixos de uma string tipicamente requer significativamente mais espaço do que armazenar a própria string.