Subcadeia de caracteres

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

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

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$); adicionalmente, algumas fontes 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.