String (ciência da computação)

Na programação de computadores, uma string é tradicionalmente uma sequência de caracteres, seja como uma constante literal ou como algum tipo de variável. Este último pode permitir que seus elementos sejam modificados e o comprimento alterado, ou pode ser corrigido (após a criação). Uma string é geralmente considerada um tipo de dados e geralmente é implementada como uma estrutura de dados de array de bytes (ou palavras) que armazena uma sequência de elementos, normalmente caracteres, usando alguma codificação de caracteres. String também pode denotar matrizes mais gerais ou outros tipos e estruturas de dados de sequência (ou lista).

Dependendo da linguagem de programação e do tipo de dados preciso usado, uma variável declarada como uma string pode fazer com que o armazenamento na memória seja alocado estaticamente para um comprimento máximo predeterminado ou empregar alocação dinâmica para permitir que ela contenha um número variável de elementos.

Quando uma string aparece literalmente no código-fonte, ela é conhecida como string literal ou string anônima.

Em linguagens formais, usadas na lógica matemática e na ciência da computação teórica, uma string é uma sequência finita de símbolos escolhidos de um conjunto chamado alfabeto.

Propósito

O objetivo principal das strings é armazenar texto legível por humanos, como palavras e frases. Strings são usadas para comunicar informações de um programa de computador ao usuário do programa. Um programa também pode aceitar entrada de string de seu usuário. Além disso, as strings podem armazenar dados expressos como caracteres, mas não destinados à leitura humana.

Exemplos de strings e suas finalidades:

• Uma mensagem como "file upload complete" é uma string que o software mostra aos usuários finais. No código fonte do programa, esta mensagem provavelmente apareceria como uma cadeia literal.
• Texto inserido pelo usuário, como "I got a new job today" como uma atualização de status em um serviço de mídia social. Em vez de uma cadeia de caracteres literal, o software provavelmente armazenaria esta cadeia de caracteres em um banco de dados.
• Dados alfabéticos, como "AGATGCCGT" representando sequências de ácido nucleico do DNA.
• Configurações do computador ou parâmetros, como "?action=edit" como uma string de consulta de URL. Muitas vezes, estes são destinados a ser um tanto legível humano, embora o seu principal objetivo é se comunicar aos computadores.

O termo string também pode designar uma sequência de dados ou registros de computador que não sejam caracteres — como uma "sequência de bits" — mas quando usado sem qualificação refere-se a sequências de caracteres.

Histórico

O uso da palavra "string" significar quaisquer itens organizados em uma linha, série ou sucessão remonta a séculos. Na composição tipográfica do século 19, os compositores usavam o termo "string" para denotar um comprimento de tipo impresso em papel; a string seria medida para determinar o pagamento do compositor.

O uso da palavra "string" significar "uma sequência de símbolos ou elementos linguísticos em uma ordem definida" emergiu da matemática, da lógica simbólica e da teoria linguística para falar sobre o comportamento formal dos sistemas simbólicos, deixando de lado os símbolos & # 39; significado.

Por exemplo, o lógico C. I. Lewis escreveu em 1918:

Um sistema matemático é qualquer conjunto de cadeias de marcas reconhecíveis em que algumas das cordas são tomadas inicialmente e o restante derivado destas por operações realizadas de acordo com as regras que são independentes de qualquer significado atribuído às marcas. Que um sistema deve consistir de 'marcas' em vez de sons ou odores é immaterial.

De acordo com Jean E. Sammet, "a primeira linguagem realista de manipulação de strings e correspondência de padrões" para computadores foi o COMIT na década de 1950, seguido pela linguagem SNOBOL do início dos anos 1960.

Tipos de dados de string

Um tipo de dados string é um tipo de dados modelado na ideia de uma string formal. Strings são um tipo de dados tão importante e útil que são implementados em quase todas as linguagens de programação. Em algumas linguagens eles estão disponíveis como tipos primitivos e em outras como tipos compostos. A sintaxe da maioria das linguagens de programação de alto nível permite que uma string, geralmente citada de alguma forma, represente uma instância de um tipo de dados string; tal meta-string é chamada de literal ou string literal.

Comprimento da string

Embora strings formais possam ter um comprimento finito arbitrário, o comprimento das strings em linguagens reais é frequentemente restrito a um máximo artificial. Em geral, existem dois tipos de tipos de dados de string: strings de comprimento fixo, que têm um comprimento máximo fixo a ser determinado em tempo de compilação e que usam a mesma quantidade de memória, seja esse máximo necessário ou não. e strings de comprimento variável, cujo comprimento não é fixo arbitrariamente e que podem usar quantidades variadas de memória dependendo dos requisitos reais em tempo de execução (consulte Gerenciamento de memória). A maioria das strings nas linguagens de programação modernas são strings de comprimento variável. É claro que mesmo strings de comprimento variável têm comprimento limitado – pelo tamanho da memória disponível do computador. O comprimento da string pode ser armazenado como um número inteiro separado (o que pode colocar outro limite artificial no comprimento) ou implicitamente através de um caractere de terminação, geralmente um valor de caractere com todos os bits zero, como na linguagem de programação C. Consulte também "Terminação nula" abaixo.

Codificação de caracteres

Os tipos de dados String alocaram historicamente um byte por caractere e, embora o conjunto exato de caracteres variasse por região, as codificações de caracteres eram semelhantes o suficiente para que os programadores muitas vezes ignorassem isso, uma vez que os caracteres que um programa tratava especialmente (como ponto e espaço e vírgula) estavam no mesmo lugar em todas as codificações que um programa encontraria. Esses conjuntos de caracteres eram normalmente baseados em ASCII ou EBCDIC. Se o texto em uma codificação fosse exibido em um sistema usando uma codificação diferente, o texto era frequentemente distorcido, embora muitas vezes um tanto legível, e alguns usuários de computador aprendiam a ler o texto distorcido.

Idiomas logográficos como chinês, japonês e coreano (conhecidos coletivamente como CJK) precisam de muito mais do que 256 caracteres (o limite de uma codificação de um byte de 8 bits por caractere) para uma representação razoável. As soluções normais envolviam manter representações de byte único para ASCII e usar representações de dois bytes para ideogramas CJK. O uso deles com o código existente levou a problemas de correspondência e corte de strings, cuja gravidade dependia de como a codificação de caracteres foi projetada. Algumas codificações, como a família EUC, garantem que um valor de byte no intervalo ASCII representará apenas aquele caractere ASCII, tornando a codificação segura para sistemas que usam esses caracteres como separadores de campos. Outras codificações, como ISO-2022 e Shift-JIS, não oferecem tais garantias, tornando insegura a correspondência em códigos de bytes. Essas codificações também não eram 'autossincronizadas', de modo que a localização dos limites dos caracteres exigia o backup do início de uma string, e colar duas strings juntas poderia resultar na corrupção da segunda string.

O Unicode simplificou um pouco o quadro. A maioria das linguagens de programação agora possui um tipo de dados para strings Unicode. O formato de fluxo de bytes UTF-8 preferido do Unicode foi projetado para não ter os problemas descritos acima para codificações multibyte mais antigas. UTF-8, UTF-16 e UTF-32 exigem que o programador saiba que as unidades de código de tamanho fixo são diferentes dos "caracteres", a principal dificuldade atualmente são APIs projetadas incorretamente que tentam esconder essa diferença (UTF-32 cria pontos de código de tamanho fixo, mas estes não são 'caracteres' devido à composição de códigos).

Implementações

Algumas linguagens, como C++, Perl e Ruby, normalmente permitem que o conteúdo de uma string seja alterado após sua criação; elas são chamadas de strings mutáveis. Em outras linguagens, como Java, JavaScript, Lua, Python e Go, o valor é fixo e uma nova string deve ser criada caso alguma alteração seja feita; elas são chamadas de strings imutáveis. Algumas dessas linguagens com strings imutáveis também fornecem outro tipo que é mutável, como o StringBuilder do Java e do.NET, o StringBuffer do Java thread-safe e o Cacau NSMutableString. Existem vantagens e desvantagens na imutabilidade: embora strings imutáveis possam exigir a criação ineficiente de muitas cópias, elas são mais simples e completamente seguras para threads.

Strings normalmente são implementadas como matrizes de bytes, caracteres ou unidades de código, para permitir acesso rápido a unidades ou substrings individuais — incluindo caracteres quando eles têm comprimento fixo. Algumas linguagens como Haskell as implementam como listas vinculadas.

Algumas linguagens, como Prolog e Erlang, evitam implementar um tipo de dados de string dedicado, em vez disso adotam a convenção de representar strings como listas de códigos de caracteres.

Representações

As representações de strings dependem muito da escolha do repertório de caracteres e do método de codificação de caracteres. Implementações de strings mais antigas foram projetadas para funcionar com repertório e codificação definidos por ASCII, ou extensões mais recentes como a série ISO 8859. As implementações modernas geralmente usam o extenso repertório definido pelo Unicode junto com uma variedade de codificações complexas, como UTF-8 e UTF-16.

O termo sequência de bytes geralmente indica uma sequência de bytes de uso geral, em vez de sequências de apenas caracteres (legíveis), sequências de bits ou algo semelhante. As cadeias de bytes geralmente implicam que os bytes podem assumir qualquer valor e quaisquer dados podem ser armazenados como estão, o que significa que não deve haver nenhum valor interpretado como um valor de terminação.

A maioria das implementações de strings são muito semelhantes a arrays de comprimento variável, com as entradas armazenando os códigos dos caracteres correspondentes. A principal diferença é que, com certas codificações, um único caractere lógico pode ocupar mais de uma entrada no array. Isso acontece, por exemplo, com UTF-8, onde códigos únicos (pontos de código UCS) podem levar de um a quatro bytes, e caracteres únicos podem levar um número arbitrário de códigos. Nestes casos, o comprimento lógico da string (número de caracteres) difere do comprimento físico do array (número de bytes em uso). O UTF-32 evita a primeira parte do problema.

Terminado nulo

O comprimento de uma string pode ser armazenado implicitamente usando um caractere de terminação especial; muitas vezes este é o caractere nulo (NUL), que tem todos os bits zero, uma convenção usada e perpetuada pela popular linguagem de programação C. Portanto, essa representação é comumente chamada de string C. Esta representação de uma string de n caracteres ocupa n + 1 espaço (1 para o terminador) e é, portanto, uma estrutura de dados implícita.

Em strings terminadas, o código de terminação não é um caractere permitido em nenhuma string. Strings com campo length não possuem essa limitação e também podem armazenar dados binários arbitrários.

Um exemplo de uma string terminada em nulo armazenada em um buffer de 10 bytes, junto com sua representação ASCII (ou UTF-8 mais moderno) como números hexadecimais de 8 bits é:

O comprimento da string no exemplo acima, "FRANK", é de 5 caracteres, mas ocupa 6 bytes. Os caracteres após o terminador não fazem parte da representação; eles podem fazer parte de outros dados ou apenas lixo. (Strings neste formato às vezes são chamadas de strings ASCIZ, em homenagem à diretiva original da linguagem assembly usada para declará-las.)

Terminado em bytes e bits

O uso de um byte especial diferente de nulo para terminar strings tem aparecido historicamente tanto em hardware quanto em software, embora às vezes com um valor que também era um caractere de impressão. $ foi usado por muitos sistemas assembler, : usado por sistemas CDC (este caractere tinha valor zero), e o ZX80 usou " já que este era o delimitador de string em sua linguagem BASIC.

Um pouco semelhante, "processamento de dados" máquinas como o IBM 1401 usavam uma marca nominativa especial para delimitar as strings à esquerda, onde a operação começaria à direita. Essa parte tinha que ficar clara em todas as outras partes da string. Isso significava que, embora o IBM 1401 tivesse uma palavra de sete bits, quase ninguém pensou em usar isso como um recurso e substituir a atribuição do sétimo bit para (por exemplo) lidar com códigos ASCII.

Os primeiros softwares de microcomputadores baseavam-se no fato de que os códigos ASCII não usavam o bit de ordem superior e o configuravam para indicar o final de uma string. Deve ser redefinido para 0 antes da saída.

Prefixo de comprimento

O comprimento de uma string também pode ser armazenado explicitamente, por exemplo, prefixando a string com o comprimento como um valor de byte. Esta convenção é usada em muitos dialetos Pascal; como consequência, algumas pessoas chamam essa string de string Pascal ou string P. Armazenar o comprimento da string como byte limita o comprimento máximo da string a 255. Para evitar tais limitações, implementações aprimoradas de strings P usam palavras de 16, 32 ou 64 bits para armazenar o comprimento da string. Quando o campo comprimento cobre o espaço de endereço, as strings são limitadas apenas pela memória disponível.

Se o comprimento for limitado, então ele pode ser codificado em espaço constante, normalmente uma palavra de máquina, levando assim a uma estrutura de dados implícita, ocupando espaço n + k, onde k é o número de caracteres em uma palavra (8 para ASCII de 8 bits em uma máquina de 64 bits, 1 para UTF-32/UCS-4 de 32 bits em uma máquina de 32 bits, etc.). Se o comprimento não for limitado, a codificação de um comprimento n ocupa espaço log(n) (consulte o código de comprimento fixo), portanto, strings com prefixo de comprimento são uma estrutura de dados sucinta, codificando uma string de comprimento n em log(n) + espaço n.

No último caso, o campo de prefixo de comprimento em si não tem comprimento fixo, portanto, os dados reais da string precisam ser movidos quando a string cresce de tal forma que o campo de comprimento precisa ser aumentado.

Aqui está uma string Pascal armazenada em um buffer de 10 bytes, junto com sua representação ASCII/UTF-8:

Strings como registros

Muitas linguagens, incluindo as orientadas a objetos, implementam strings como registros com uma estrutura interna como:

classe string ( tamanho_t comprimento; Charlie. *texto;}

No entanto, como a implementação geralmente fica oculta, a string deve ser acessada e modificada por meio de funções-membro. text é um ponteiro para uma área de memória alocada dinamicamente, que pode ser expandida conforme necessário. Consulte também string (C++).

Outras representações

Tanto a terminação de caracteres quanto os códigos de comprimento limitam strings: por exemplo, matrizes de caracteres C que contêm caracteres nulos (NUL) não podem ser manipuladas diretamente pelas funções da biblioteca de strings C: Strings que usam um código de comprimento são limitadas ao valor máximo do código de comprimento.

Essas duas limitações podem ser superadas por meio de uma programação inteligente.

É possível criar estruturas de dados e funções que os manipulem sem os problemas associados à terminação de caracteres e que possam, em princípio, superar os limites de comprimento do código. Também é possível otimizar a string representada usando técnicas de codificação de comprimento de execução (substituindo caracteres repetidos pelo valor do caractere e um comprimento) e codificação de Hamming.

Embora essas representações sejam comuns, outras são possíveis. O uso de cordas torna certas operações de string, como inserções, exclusões e concatenações mais eficientes.

A estrutura de dados central em um editor de texto é aquela que gerencia a string (sequência de caracteres) que representa o estado atual do arquivo que está sendo editado. Embora esse estado possa ser armazenado em uma única matriz longa e consecutiva de caracteres, um editor de texto típico usa uma representação alternativa como sua estrutura de dados de sequência - um buffer de lacuna, uma lista vinculada de linhas, uma tabela de peças ou uma corda - o que torna certas operações de string, como inserções, exclusões e desfazer edições anteriores, são mais eficientes.

Preocupações de segurança

Os diferentes layouts de memória e requisitos de armazenamento das strings podem afetar a segurança do programa que acessa os dados da string. Representações de string que exigem um caractere de terminação são comumente suscetíveis a problemas de buffer overflow se o caractere de terminação não estiver presente, causado por um erro de codificação ou por um invasor alterando deliberadamente os dados. As representações de string que adotam um campo de comprimento separado também são suscetíveis se o comprimento puder ser manipulado. Nesses casos, o código do programa que acessa os dados da string requer verificação de limites para garantir que ele não acesse ou altere inadvertidamente dados fora dos limites de memória da string.

Os dados de string são frequentemente obtidos da entrada do usuário em um programa. Como tal, é responsabilidade do programa validar a string para garantir que ela representa o formato esperado. A execução limitada ou nenhuma validação da entrada do usuário pode tornar um programa vulnerável a ataques de injeção de código.

Sequências literais

Às vezes, as strings precisam ser incorporadas em um arquivo de texto que seja legível por humanos e destinado ao consumo por uma máquina. Isso é necessário, por exemplo, no código-fonte de linguagens de programação ou em arquivos de configuração. Nesse caso, o caractere NUL não funciona bem como terminador, pois normalmente é invisível (não imprimível) e é difícil de inserir por meio de um teclado. Armazenar o comprimento da string também seria inconveniente, pois o cálculo manual e o rastreamento do comprimento são tediosos e sujeitos a erros.

Duas representações comuns são:

• Rodeado por aspas (ASCII 0x22 cotação dupla "str" ou ASCII 0x27 cotação única 'str'), usado pela maioria das linguagens de programação. Para ser capaz de incluir caracteres especiais, como a própria marca de cotação, caracteres de linha nova ou caracteres não imprimíveis, as sequências de fuga estão muitas vezes disponíveis, geralmente prefixadas com o caractere backslash (ASCII 0x5C).
• Terminado por uma sequência de linha nova, por exemplo nos arquivos do Windows INI.

Sequências não textuais

Embora strings de caracteres sejam usos muito comuns de strings, uma string na ciência da computação pode se referir genericamente a qualquer sequência de dados digitados homogeneamente. Uma sequência de bits ou sequência de bytes, por exemplo, pode ser usada para representar dados binários não textuais recuperados de um meio de comunicação. Esses dados podem ou não ser representados por um tipo de dados específico de string, dependendo das necessidades da aplicação, do desejo do programador e dos recursos da linguagem de programação usada. Se a implementação da string da linguagem de programação não for limpa de 8 bits, poderá ocorrer corrupção de dados.

Os programadores C fazem uma distinção nítida entre uma "string", também conhecida como uma "string de caracteres", que por definição é sempre terminada em nulo, e uma "string de bytes&' #34; ou "pseudo string" que pode ser armazenado na mesma matriz, mas geralmente não é terminado em nulo. Usando funções de manipulação de string C em uma "string de bytes" muitas vezes parece funcionar, mas depois leva a problemas de segurança.

Algoritmos de processamento de strings

Existem muitos algoritmos para processamento de strings, cada um com diversas vantagens. Algoritmos concorrentes podem ser analisados em relação ao tempo de execução, requisitos de armazenamento e assim por diante. O nome stringologia foi cunhado em 1984 pelo cientista da computação Zvi Galil para a teoria de algoritmos e estruturas de dados usadas para processamento de strings.

Algumas categorias de algoritmos incluem:

• String procurando algoritmos para encontrar uma substring dada ou padrão
• Algoritmos de manipulação de cordas
• Seleção de algoritmos
• Algoritmos de expressão regular
• Parsing a string
• Mineração de sequência

Algoritmos de string avançados geralmente empregam mecanismos e estruturas de dados complexos, entre eles árvores de sufixos e máquinas de estado finito.

Linguagens e utilitários orientados a strings de caracteres

Strings de caracteres são um tipo de dados tão útil que diversas linguagens foram projetadas para facilitar a escrita de aplicativos de processamento de strings. Os exemplos incluem os seguintes idiomas:

• Awk
• Ícone
• MUMPS
• Perl
• Rexxx
• Ruby!
• Segurem-se.
• SNOBOL
• TC
• TTM

Muitos utilitários Unix realizam manipulações simples de strings e podem ser usados para programar facilmente alguns poderosos algoritmos de processamento de strings. Arquivos e fluxos finitos podem ser vistos como strings.

Algumas APIs como Multimedia Control Interface, SQL incorporado ou printf usam strings para armazenar comandos que serão interpretados.

Muitas linguagens de programação de script, incluindo Perl, Python, Ruby e Tcl, empregam expressões regulares para facilitar operações de texto. Perl é particularmente conhecido por seu uso de expressões regulares, e muitas outras linguagens e aplicações implementam expressões regulares compatíveis com Perl.

Algumas linguagens como Perl e Ruby suportam interpolação de strings, o que permite que expressões arbitrárias sejam avaliadas e incluídas em literais de strings.

Funções de cadeia de caracteres

As funções de string são usadas para criar strings ou alterar o conteúdo de uma string mutável. Eles também são usados para consultar informações sobre uma string. O conjunto de funções e seus nomes variam dependendo da linguagem de programação do computador.

O exemplo mais básico de uma função de string é a função de comprimento de string – a função que retorna o comprimento de uma string (sem contar quaisquer caracteres terminadores ou qualquer informação estrutural interna da string) e não modifica o corda. Esta função geralmente é chamada de length ou len. Por exemplo, length("hello world") retornaria 11. Outra função comum é a concatenação, onde uma nova string é criada anexando duas strings, geralmente este é o operador de adição +.

Algumas arquiteturas de conjunto de instruções de microprocessadores contêm suporte direto para operações de string, como cópia de bloco (por exemplo, em Intel x86m REPNZ MOVSB).

Teoria formal

Seja Σ um conjunto finito de símbolos (alternativamente chamados de caracteres), chamado alfabeto. Nenhuma suposição é feita sobre a natureza dos símbolos. Uma string (ou palavra) sobre Σ é qualquer sequência finita de símbolos de Σ. Por exemplo, se Σ = {0, 1}, então 01011 é uma string sobre Σ.

O comprimento de uma string s é o número de símbolos em s (o comprimento da sequência) e pode ser qualquer número não- inteiro negativo; geralmente é denotado como |s|. A string vazia é a string única sobre Σ de comprimento 0 e é denotada como ε ou λ.

O conjunto de todas as strings acima de Σ de comprimento n é denotado Σn. Por exemplo, se Σ = {0, 1}, então Σ2 = {00, 01, 10, 11}. Observe que Σ0 = {ε} para qualquer alfabeto Σ.

O conjunto de todas as strings sobre Σ de qualquer comprimento é o fechamento de Kleene de Σ e é denotado Σ*. Em termos de Σn,

$Não. Sigma ^{*}=bigcup _{nin mathbb {N} cup {0}}\ Sigma ^{n}}$

Por exemplo, se Σ = {0, 1}, então Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,...}. Embora o próprio conjunto Σ* seja contávelmente infinito, cada elemento de Σ* é uma string de comprimento finito.

Um conjunto de strings sobre Σ (ou seja, qualquer subconjunto de Σ*) é chamado de linguagem formal sobre Σ. Por exemplo, se Σ = {0, 1}, o conjunto de strings com um número par de zeros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111,...}, é uma linguagem formal sobre Σ.

Concatenação e substrings

Concatenação é uma operação binária importante em Σ*. Para quaisquer duas strings s e t em Σ*, sua concatenação é definida como a sequência de símbolos em s seguido pela sequência de caracteres em t e é denotado como st. Por exemplo, se Σ = {a, b,..., z}, s = bear e t = abraço e então st = bearhug e ts = abraço.

A concatenação é uma operação associativa, mas não comutativa. A string vazia ε serve como elemento de identidade; para qualquer string S, εS = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sε = S. Portanto, o conjunto Σ* e a operação de concatenação formam um monoide, o monoide livre gerado por Σ. Além disso, a função de comprimento define um homomorfismo monoide de Σ* para os inteiros não negativos (isto é, uma função $Não. L:Sigma ^{*}mapsto mathbb {N} cup {0}}$, tal que ${displaystyle L(st)=L(s)+L(t)quad forall s,tin Sigma ^{*}}$).

Uma string s é considerada uma substring ou fator de t se existir (possivelmente vazia) strings u e v tais que t = usv. A relação "é uma substring de" define uma ordem parcial em Σ*, cujo menor elemento é a string vazia.

Prefixos e sufixos

Uma string s é considerada um prefixo de t se existe uma string u tal que t = su. Se u não estiver vazio, diz-se que s é um prefixo próprio de t. Simetricamente, uma string s é considerada um sufixo de t se existe uma string u tal que t = nós. Se u não for vazio, diz-se que s é um sufixo próprio de t. Sufixos e prefixos são substrings de t. Ambas as relações "é um prefixo de" e "é um sufixo de" são ordens de prefixo.

Reversão

O reverso de uma string é uma string com os mesmos símbolos, mas na ordem inversa. Por exemplo, se s = abc (onde a, b e c são símbolos do alfabeto), então o inverso de s é cba. Uma string que é o inverso de si mesma (por exemplo, s = madame) é chamada de palíndromo, que também inclui a string vazia e todas as strings de comprimento 1.

Rotações

Uma string s = uv é considerada uma rotação de t se t = vu. Por exemplo, se Σ = {0, 1} a string 0011001 é uma rotação de 0100110, onde u = 00110 e v = 01. Como outro exemplo, a string abc tem três rotações diferentes, viz. abc em si (com u=abc, v=ε), bca (com u=bc, v= a) e cab (com u=c, v=ab).

Ordenação lexicográfica

Muitas vezes é útil definir uma ordem em um conjunto de strings. Se o alfabeto Σ tiver uma ordem total (cf. ordem alfabética) pode-se definir uma ordem total em Σ* chamada ordem lexicográfica. A ordem lexicográfica é total se a ordem alfabética o for, mas não é bem fundamentada para qualquer alfabeto não trivial, mesmo que a ordem alfabética o seja. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordem lexicográfica em Σ* inclui as relações ε < 0 < 00 < 000 <... < 0001 <... < 001 <...< 01 < 010 <... < 011 < 0110 <...< 01111 <...< 1 < 10 < 100 <... < 101 <...< 111 <...< 1111 <...< 11111... Com relação a esta ordem, por ex. o conjunto infinito { 1, 01, 001, 0001, 00001, 000001,... } não possui elemento mínimo.

Veja Shortlex para uma ordenação alternativa de strings que preserva a fundamentação. Para o alfabeto de exemplo, a ordem shortlex é ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 <... < 1111 < 00000 < 00001...

Operações de string

Uma série de operações adicionais em strings comumente ocorrem na teoria formal. Eles são fornecidos no artigo sobre operações com strings.

Topologia

Strings admitem a seguinte interpretação como nós em um grafo, onde k é o número de símbolos em Σ:

• Cordas de comprimento fixo de comprimento n pode ser visto como os locais inteiros em um nHipercubo dimensional com lados de comprimento k-1.
• Cordas de comprimento variável (de comprimento finito) podem ser vistas como nós em uma árvore k-ary perfeita.
• Cordas infinitas (não consideradas aqui) podem ser vistas como caminhos infinitos em um k-node gráfico completo.

A topologia natural no conjunto de cadeias de comprimento fixo ou de comprimento variável é a topologia discreta, mas a topologia natural no conjunto de cadeias infinitas é a topologia limite, vendo o conjunto de cadeias infinitas como o limite inverso de os conjuntos de cordas finitas. Esta é a construção usada para os números p-ádicos e algumas construções do conjunto de Cantor, e produz a mesma topologia.

Isomorfismos entre representações de strings de topologias podem ser encontrados normalizando de acordo com a rotação lexicograficamente mínima de strings.