Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.[1]
Nas maioria das linguagens de programação, as cadeias de caracteres podem ser expressas tanto na forma literal, como através de algum tipo de variável. Quando expressos através de variáveis, o conteúdo da cadeia geralmente pode ser alterado pela inclusão/exclusão de elementos ou pela substituição de seus elementos por outros elementos, formando uma nova cadeia. Assim, uma cadeia de caracteres é vista como sendo um tipo de dado e normalmente é implementada através de um arranjo de bytes que armazena os elementos da cadeia em sequência, utilizando alguma codificação preestabelecida.[2]
Nas linguagens formais, uma cadeia de caracteres é uma sequência finita de símbolos escolhidos a partir de conjunto denominado alfabeto.[2]
Seja Σ um conjunto finito e não vazio de símbolos (ou caracteres) chamado de o alfabeto. Uma cadeia sobre Σ é qualquer sequência finita de caracteres contidos em Σ.[3]
- Se o alfabeto Σ = {0, 1}, então 0, 1, 01, 000001 e 101 são cadeias sobre o alfabeto Σ.
O comprimento ou cardinalidade da cadeia é a quantidade de caracteres utilizados para sua composição. À cadeia de comprimento zero dá-se o nome de cadeia vazia e é usualmente denotada na literatura pelos símbolos ε ou λ.
- Se o alfabeto Σ = {0, 1}, então |00| = 2, |0101| = 4 e |ε| = 0.'
O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σn.
- Se o alfabeto Σ = {0, 1}, então Σ² = {00, 01, 10, 11}. Notar que Σ0 = {ε} para qualquer alfabeto Σ.
O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, Σ* = Σ0 ∪ Σ1 ∪ Σ2….
- Se o alfabeto Σ = {0, 1} então Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}.
Apesar do conjunto Σ* possuir infinitos elementos, todos os elementos de Σ* possuem comprimento finito.
Um conjunto de cadeias sobre um alfabeto Σ (isto é, qualquer subconjunto de Σ*) é chamado de linguagem formal sobre Σ.
Concatenação e sub-cadeias
Concatenação é uma importante operação binária em Σ*. Para qualquer duas cadeias s e t em Σ*, sua concatenação é definida pela sequência de caracteres de s seguida pela sequência de caracteres em t, denotada por st. Por exemplo se Σ = {a, b, …, z}, s = bear e t = hug, então st = bearhug e ts = hugbear.
A concatenação de cadeias é uma operação associativa, mas não comutativa. A cadeia vazia serve como um elemento identidade: para qualquer cadeia s, εs = sε = s. Portanto, o conjunto Σ* e a operação de concatenação formam um monóide.
A cadeia s é dita uma subcadeia (ou fator) de t se existem cadeias (possivelmente vazias) u e v de forma que t = usv.
Ordenação lexicográfica
Geralmente é necessário definir uma ordenação em um conjunto de cadeias. Se um alfabeto Σ possui uma relação de ordem (como a ordem alfabética) pode-se definir uma relação de ordem em Σ* chamada ordem lexicográfica. Note que como Σ é finito, é sempre possível definir uma ordenação em Σ e portanto em Σ*. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordenação lexicográfica em Σ* é ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …
Cadeia de caracteres como tipo de dado
Um tipo de dado cadeia de caracteres (referido em programação geralmente como string) é uma modelagem de uma cadeia formal de caracteres. São bastante usados em programação, sendo implementados em quase todas as linguagens de programação. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado.
Referências
