Subcadeia de caracteres

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 .

SubcadeiaEditar

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.

PrefixoEditar

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ênciasEditar

  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