Subcadeia de caracteres

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou seçã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 é outra cadeia que ocorre dentro de . 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 é uma subcadeia de que ocorre no início de . Um sufixo de uma cadeia é uma subcadeia que ocorre no final de .

Subcadeia[editar | editar código-fonte]

Uma subcadeia (ou fator) de uma cadeia é uma cadeia , onde e . Uma subcadeia de uma cadeia é um prefixo de um sufixo da cadeia, e equivalentemente, uma sufixo de um prefixo. Se é uma subcadeia de , também é uma subsequência, que é um conceito mais geral. Dado um padrão , você pode encontrar suas ocorrências em uma cadeia 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 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 de tais lugares. Então, existem subcadeias não-vazias.

Prefixo[editar | editar código-fonte]

Um prefixo de uma cadeia é uma cadeia , onde . Um prefixo adequado de uma cadeia não é igual a própria cadeia ();[1] adicionalmente, algumas fontes[2] restringem um prefixo adequado a ser não-vazio (). 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 denota que é um prefixo de . 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 (1995). Automata and Formal Languages: An Introduction (London: Prentice-Hall International). ISBN 0-13-497777-7. 
  2. Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology (USA: Cambridge University Press). ISBN 0-521-58519-8.