Substring - Substring

" string " é uma substring de " 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 . ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

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. ${\ displaystyle u}$${\ displaystyle t}$${\ displaystyle p}$${\ displaystyle s}$${\ displaystyle t = pus}$

Exemplo: a string é igual a substrings (e subsequências) de em dois deslocamentos diferentes: ${\ displaystyle u =}$ana${\ displaystyle t =}$banana

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

A primeira ocorrência é obtida com e , enquanto a segunda ocorrência é obtida com e sendo a string vazia. ${\ displaystyle p =}$b${\ displaystyle s =}$na${\ displaystyle p =}$ban${\ displaystyle s}$

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). ${\ displaystyle u}$${\ displaystyle t}$

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. ${\ displaystyle p}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t = ps}$

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 . ${\ displaystyle p \ sqsubseteq t}$${\ displaystyle p}$${\ displaystyle t}$

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. ${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle p}$${\ displaystyle t = ps}$

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 . ${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle {\ text {bcclabccefab}}}$${\ displaystyle P = \ {{\ text {abcc}}, {\ text {efab}}, {\ text {bccla}} \}}$${\ displaystyle {\ text {efabccla}}}$${\ displaystyle P}$${\ displaystyle P}$

Veja também

• Notação de chave
• Índice de substring
• Sufixo autômato

Referências

links externos

• Mídia relacionada a substring no Wikimedia Commons