Subcadeia de caracteres

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido (desde janeiro de 2014). Ajude e colabore com a tradução.

Uma subcadeia (também chamada substring) de uma cadeia de caracteres S é outra cadeia S' que ocorre dentro de S. Por exemplo, "o melhor dos" é uma subcadeia de "Foi o melhor dos tempos". Não deve ser confundido com subsequência, que é uma generalização de subcadeia. Por exemplo, "Foitempos" é uma subsequência de "Foi o melhor dos tempos", mas não é uma subcadeia.

Prefixo e sufixos são refinamentos de uma subcadeia. Um prefixo de uma cadeia S é uma subcadeia de S que ocorre no início de S. Um sufixo de uma cadeia S é uma subcadeia que ocorre no final de S.

Subcadeia[editar | editar código-fonte]

Uma subcadeia (ou fator) de uma cadeia T = t_1 \dots t_n é uma cadeia \hat T = t_{1+i} \dots t_{m+i}, onde 0 \leq i e m + i \leq n. Uma subcadeia de uma cadeia é um prefixo de um sufixo da cadeia, e equivalentemente, uma sufixo de um prefixo. Se \hat T é uma subcadeia de T, também é uma subsequência, que é um conceito mais geral. Dado um padrão P, você pode encontrar suas ocorrências em uma cadeia T com um algoritmo de busca por cadeias de caracteres. Encontrar a maior cadeia que é igual a subcadeia de duas ou mais cadeias é conhecido como o problema da maior subcadeia comum.

Exemplo: a cadeia ana é igual às subcadeias (e subsequências) de banana em duas diferentes posições:

banana
 |||||
 ana||
   |||
   ana

Na literatura matemática, substrings também são denominadas subpalavras (na América) ou fatores (na Europa).

Não incluindo a subcadeia vazia, o número de subcadeias de uma cadeia de tamanho n onde os símbolos ocorrem apenas uma vez, é o número de maneiras de escolher dois lugares distintos para os símbolos inicial/final da subcadeia. Incluindo o início e o final da cadeia, existem n+1 de tais lugares. Então, existem \tbinom{n+1}{2} = \tfrac{n(n+1)}{2} subcadeias não-vazias.

Prefixo[editar | editar código-fonte]

Um prefixo de uma cadeia T = t_1 \dots t_n é uma cadeia \widehat T = t_1 \dots t_{m}, onde m \leq n. Um prefixo adequado de uma cadeia não é igual a própria cadeia (0 \leq m < n);[1] adicionalmente, algumas fontes[2] restringem um prefixo adequado a ser não-vazio (0 < m < n). Um prefixo pode ser visto como um caso especial de uma subcadeia.

Exemplo: A cadeia ban é igual ao prefixo (e subcadeia e subsequência) da cadeia banana:

banana
|||
ban

O símbolo de subconjunto quadrado é, às vezes, usado para indicar um prefixo, logo \widehat T \sqsubseteq T denota que \widehat T é um prefixo de T. Isto define uma relação binária sobre cadeias, chamada relação de prefixos, que é um tipo particular de ordem de prefixos.

Na teoria de linguagens formais, o termo prefixo de uma cadeia também é comumente entendido por ser o conjunto de todos os prefixos de uma cadeia, com respeito àquela linguagem. Veja o artigo em operações sobre cadeias para mais detalhes.

Referências[editar | editar código-fonte]

  1. Kelley, Dean. Automata and Formal Languages: An Introduction. London: Prentice-Hall International, 1995. ISBN 0-13-497777-7.
  2. Gusfield, Dan. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press, 1999. ISBN 0-521-58519-8.