Algoritmos de Cadeias de Caracteres

Uma cadeia de caracteres sobre Σ é uma sequência finita de símbolos. A estrutura deste tópico é a trie: índice de um conjunto de cadeias em que cada palavra é um caminho a partir da raiz, e prefixos iguais compartilham o trecho inicial.

Inserir, buscar e consultar prefixo nesta página — e a árvore de sufixos, trie compactada dos sufixos de uma só cadeia S — partem desse caminho rotulado.

As páginas se agrupam em quatro blocos. O primeiro monta a trie: aresta leva um símbolo de Σ, bit terminal marca palavra completa, e inserir ou buscar w custa proporcional a |w|.

O segundo pergunta se alguma palavra do conjunto começa com o prefixo u e lista as extensões na subárvore daquele nó.

O terceiro trata do sufixo: a primeira aresta é a primeira letra da palavra, então inho não é caminho a partir da raiz.

O quarto compacta todos os sufixos de uma cadeia S numa árvore de sufixos, para decidir se P ocorre em S.

Inserir gato e galo compartilhando ga, ou decidir se cabra está no conjunto pelo bit terminal do último nó, está em Tries e Processamento de Texto.

Consultar se alguma palavra começa com ca — o nó existe, sem marca terminal — está em Tries e Processamento de Texto. As palavras casa, cabra e carro pendem da subárvore.

A consulta do sufixo inho a partir da raiz está em Tries e Processamento de Texto. amor e amorzinho compartilham o começo; os dois inho pendem de caminhos distintos.

Decidir se P ocorre em uma cadeia S está na árvore de sufixos, em Tries e Processamento de Texto. O conjunto {amor, amorzinho, beijinho} permanece na trie.