Substring - Substring
Na teoria da linguagem formal e na ciência da computação , uma substring é uma sequência contígua de caracteres dentro de uma string . Por exemplo, " o melhor de " é uma substring de " Foi o melhor dos tempos ". Em contraste, " Itwastimes " é uma subsequência de " Foi o melhor dos tempos ", mas não uma substring.
Prefixos e sufixos são casos especiais de substrings. Um prefixo de uma string é uma substring de que ocorre no início de ; da mesma forma, um sufixo de uma string é uma substring que ocorre no final de .
A lista de todas as substrings da string " apple " seria " apple ", " appl ", " pple ", " app ", " ppl ", " ple ", " ap ", " pp ", " pl ", " le "," a "," p "," l "," e "," "(observe a string vazia no final).
Substring
Uma string é uma substring (ou fator) de uma string se houver duas strings e tal . Em particular, a string vazia é uma substring de cada string.
Exemplo: a string é igual a substrings (e subsequências) de em dois deslocamentos diferentes:
ana
banana
banana ||||| ana|| ||| ana
A primeira ocorrência é obtida com e , enquanto a segunda ocorrência é obtida com e sendo a string vazia.
b
na
ban
Uma substring de uma string é um prefixo de um sufixo da string e, de maneira equivalente, um sufixo de um prefixo; por exemplo, nan
é um prefixo de nana
, que por sua vez é um sufixo de banana
. Se for uma substring de , também é uma subsequência , que é um conceito mais geral. As ocorrências de um determinado padrão em uma determinada string podem ser encontradas com um algoritmo de pesquisa de string . Encontrar a string mais longa que é igual a uma substring de duas ou mais strings é conhecido como o problema comum de substring mais longo . Na literatura matemática, substrings também são chamados de subwords (na América) ou fatores (na Europa).
Prefixo
Uma string é um prefixo de uma string se existir uma string assim . Um prefixo adequado de uma string não é igual à própria string; algumas fontes, além disso, restringem um prefixo adequado para não ser vazio. Um prefixo pode ser visto como um caso especial de uma substring.
Exemplo: a string ban
é igual a um prefixo (e substring e subsequência) da string banana
:
banana ||| ban
O símbolo de subconjunto de quadrados às vezes é usado para indicar um prefixo, de modo que denota que é um prefixo de . Isso define uma relação binária em strings, chamada de relação de prefixo , que é um tipo particular de ordem de prefixo .
Sufixo
Uma string é um sufixo de uma string se existir uma string assim . Um sufixo adequado de uma string não é igual à própria string. Uma interpretação mais restrita é que também não está vazio. Um sufixo pode ser visto como um caso especial de uma substring.
Exemplo: a string nana
é igual a um sufixo (e substring e subsequência) da string banana
:
banana |||| nana
Uma árvore de sufixos para uma string é uma estrutura de dados trie que representa todos os seus sufixos. As árvores de sufixo têm um grande número de aplicações em algoritmos de string . A matriz de sufixos é uma versão simplificada dessa estrutura de dados que lista as posições iniciais dos sufixos em ordem alfabética; ele tem muitos dos mesmos aplicativos.
Fronteira
Uma borda é sufixo e prefixo da mesma string, por exemplo, "bab" é uma borda de "babab" (e também de "babooneatingakebab").
Supercorda
Uma supercorda de um conjunto finito de strings é uma única string que contém todas as strings como substring. Por exemplo, é uma supercorda de e é mais curta. Geralmente, está interessado em encontrar supercordas cujo comprimento seja o menor possível; uma concatenação de todas as cadeias de em qualquer ordem fornece uma supercorda trivial de . Uma string que contém todas as permutações possíveis de um conjunto de caracteres especificado é chamada de superpermutação .
Veja também
Referências
links externos
- Mídia relacionada a substring no Wikimedia Commons