-
Notifications
You must be signed in to change notification settings - Fork 153
Algoritmos Elementares
Nesta seção são ilustrados algoritmos elementares sobre strings, com o intuito de ilustrar a manipulação, identificação e extração de informações de strings. As técnicas apresentadas servirão tanto para solidificar os conceitos fundamentais quanto para preprar o leitor para os algoritmos mais elaborados das seções subsequentes.
Palíndromos são strings que são idênticas quando lidas tanto do início para
o fim quanto do fim para o início (por exemplo, MUSSUM, SAIAS e HANNAH são
palíndromos). Mais formalmente, um palíndromo P pode ser definido como
P[1..N] = "" | P[1..1] | P[2..N-1] and P[1] == P[N],
ou seja, strings vazias, strings com um único caractere ou strings resultantes da concatenação de um mesmo caractere no ínicio e no fim de um palíndromo resulta em palíndromos.
Uma maneira de se verificar se uma string s é ou não palíndromo é checar se
o primeiro caractere coincide com o último, o segundo com o penúltimo, e assim
por diante.
bool is_palindrome(const string& s)
{
size_t N = s.size();
for (size_t i = 0; i < N; ++i)
if (s[i] != s[N - 1 - i])
return false;
return true;
}Este algoritmo tem complexidade O(N). Embora ele identifique corretamente se
s é ou não um palíndromo, é possível torná-lo mais eficiente ao observar que
só é necessário fazer tal verificação até a metade de s (pois, se i >= N/2,
temos i = N - 1 - j, j < N/2 e a comparação s[i] == s[N - 1 - i] equivale a
comparação s[N - 1 - j] == s[N - 1 - (N - 1 - j)], isto é,
s[N - 1 - j] == s[j], j < N/2. Mesmo que a complexidade permaneça O(N), a
versão abaixo executa duas vezes mais rápido que a anterior.
bool is_palindrome2(const string& s)
{
size_t N = s.size();
for (size_t i = 0; i < N/2; ++i)
if (s[i] != s[N - 1 - i])
return false;
return true;
}Observe que is_palindrome2() identifica, corretamente, strings s de tamanho
par e ímpar (verifique este fato observando como o algoritmo lida com os
caracteres centrais da strings em ambos casos).
Uma técnica, oriunda da estatística, que permite identificar características
importantes de uma strings é o histograma, que consiste em uma mapeamento
entre os caracteres do alfabeto e o número de ocorrências dos mesmos em uma
string s dada. Por exemplo, para a string "abacaxi", teríamos um histograma
h com
h['a'] = 4
h['b'] = h['c'] = h['x'] = h['i'] = 1
h[c] = 0, c not in "abcxi"
Há 3 técnicas para a construção de histogramas. A primeira delas é utilizar a
classe map do C++, que permite uma construção bastante intuitiva e fácil de
histogramas, tendo como revezes a quantidade de memória necessária (o que, em
geral, não chega a ser um problema) e a complexidade dos acessos (O(log N)
para leitura e escrita).
Abaixo segue uma implementação bastante sintética em C++11, com uso de
auto e range for.
#include <map>
std::map<char, int> histogram(const string& s)
{
std::map<char, int> h;
for (auto c : s)
++h[c];
return h;
}Uma segunda forma de gerar o histograma é utilizar um array estático com
256 posições (que cobre todos os possíveis valores de um char em C/C++).
Esta estratégia permite atualizar/consultar os valores em O(1), mas a
identificação dos caracteres com valores diferentes de zero é linear neste
array (o que, na prática, geralmente não constitui problema).
#include <cstring>
void histogram(int h[256], const string& s)
{
memset(h, 0, sizeof h);
for (auto c : s)
++h[c];
}Na implementação acima, h é um parâmetro de saída, que deve ser inicializado
com zeros no início da rotina.
A terceira e última maneira é uma otimização, em espaço, da segunda. Aqui o
vetor h deve ter o tamanho M do alfabeto, e os caracteres do alfabeto devem
ser indexados de 0 a M - 1. Se o alfabeto for constituído das letras maiúsculas
e minúsculas, estas indexação é feita de forma direta, em O(1). Caso contrário,é preciso buscar o caractere no alfabeto em O(N) (ou O(log N), se o alfabeto
estiver ordenado). Neste cenário a perda de performance é compensada pela
redução da memória necessária (esta é a abordagem mais econômica em termos de
memória).
Abaixo um exemplo onde o alfabeto é composto pelas 26 letras maiúsculas.
void histogram(int h[26], const string& s)
{
memset(h, 0, sizeof h);
for (auto c : s)
++h[c - 'A'];
}Mapas, filtros e reduções são técnicas de programação funcional que permitem alterar os elementos de um vetor, gerar um novo vetor a partir da seleção de elementos específicos de um vetor dado ou gerar um único objeto ou elemento a partir dos elementos de um vetor. Sendo uma string um vetor de caracteres, estas técnicas podem ser adaptadas para o contexto da manipulação de textos e letras.
Mapas
Um mapa (ou mapeamento) consiste em uma função m_f: S_N -> S_N, onde
S_N é o conjunto de todas as strings de tamanho N. e f: A -> A é uma
função cujo domínio é o alfabeto A, tal que se y = m_f(s), então
y[i] = f(s[i]). Em termos mais simples, m mapeia cada caractere de s
de acordo com a função f.
Por exemplo, se A é formado pelas letras alfabéticas maiúsculas e minúsculas
e f é a função toupper(), o mapeamento m_f tornaria maiúsculas todas as
letras de uma string s dada. Uma implementação possível deste mapeamento é
dada abaixo: a função uppercase() é utilizada apenas para corrigir o retorno
da função toupper() e tornar o mapeamento reutilizável. O nome smap foi
utilizado apenas para não conflitar com a classe map da biblioteca padrão
do C++.
#include <cctype>
char uppercase(char c)
{
return (char) toupper(c);
}
void smap(string& s, char (*f)(char))
{
for (size_t i = 0; i < s.size(); ++i)
s[i] = f(s[i]);
}Outra forma de implementar um mapeamento em C++ é através da função
transform(), que está declarado na biblioteca algorithm. Deve-se atentar,
porém, que ela não suporta arrays primitivos,
apenas containers. Os dois primeiros parâmetros indicam o intervalo a ser
considerado, o terceiro é o método de inserção no container que conterá o
resultado, e o último é um operador unário que recebe um elemento do container
e retorna outro de mesmo tipo.
Abaixo uma implementação da Cifra de César usando a função transform().
Observe o uso de lambda no quarto parâmetro.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string text { "cesar cipher xyz" };
string res;
transform(text.begin(), text.end(), back_inserter(res), [](char c)
{
return c == ' ' ? c : (((c - 'a') + 3) % 26) + 'a';
}
);
cout << res << endl;
return 0;
}Filtros
Um filtro f_p : S_N -> S_M consiste em uma função que gera uma string
de tamanho M <= N, a partir de uma string de tamanho N, através da seleção
dos M caracteres que cujo predicado p: A -> Bool retorna verdadeiro.
Abaixo segue uma implementação simples que seleciona as vogais de uma string dada.
#include <cctype>
bool is_vowel(char c)
{
const string vowels { "aeiou" };
return vowels.find(tolower(c)) != string::npos;
}
string filter_vowels(const string& s)
{
string v = "";
for (auto c : s)
if (is_vowel(c))
v += c;
return v;
}Outra maneira de implementar o mesmo código é utilizar a função copy_if(),
que tem sintaxe semelhante ao da função transform(). A função
remove_copy_if() tem comportamento análogo, mas copia os caracteres que
negarem o predicado.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string text { "cesar cipher xyz" };
string res;
copy_if(text.begin(), text.end(), back_inserter(res), [](char c)
{
const string vowels { "aeiou" };
return vowels.find(c) != string::npos;
}
);
cout << res << endl;
return 0;
}
Reduções
Uma redução r_b : S_N -> T gera um elemento do tipo T através da
aplicação sucessiva, do operador binário b, da esquerda para a direita, em
cada elemento de s, tendo como operador esquerdo inicial o valor passado
como parâmetro.
Uma implementação direta da redução que soma os dígitos contidos na string
s é dada abaixo.
int sum(const string& s)
{
int s = 0;
for (auto c : s)
s += (c - '0');
return s;
}Em C++, é possível utilizar a função accumulate() para reduções. O mesmo
código acima pode ser reimplementado da seguinte maneira.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string text { "12345" };
int res = accumulate(text.begin(), text.end(), 0, [](int L, int R)
{
return L + (R - '0');
}
);
cout << res << endl;
return 0;
}Observe que o uso das funções transform(), copy_if() e accumulate()
evitam o uso de laços de repetição.
Uma tabela de substituição é uma aplicação prática de um mapeamento. Ela
é definida por uma função f: A -> A que mapeia cada caractere do alfabeto A
em outro caractere do mesmo alfabeto. Sistemas criptográficos mais simples
utilizam tabelas de substituição, como a Cifra de César, já citada, e a
criptografia baseada em xor.
Abaixo segue um exemplo de criptografia xor. A tabela de substituição table
é precomputada e é utilizado um mapeamento para cifrar e decifrar as mensagens.
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 256
char table[MAX];
void fill_table(char key)
{
for (int i = 0; i < MAX; ++i)
table[i] = i ^ key;
}
string cipher(const string& text)
{
string res;
transform(text.begin(), text.end(), back_inserter(res), [](char c)
{
return table[(int) c];
}
);
return res;
}
string decipher(const string& c)
{
return cipher(c);
}
int main()
{
fill_table(0x3B);
string message { "Xor cipher example" };
string c = cipher(message);
printf("c =");
for (auto t : c)
printf(" %02x", t);
printf("\n");
string d = decipher(c);
printf("d = [%s]\n", d.c_str());
return 0;
}Tokenização é o processo de quebra de um texto em palavras, frases, símbolos, etc, denominados tokens. Para realizar a tokenização, é necessário primeiramente definir precisamente um token, e esta definição depende do contexto onde os tokens serão utilizados.
Uma abordagem simples é definir uma lista de caracteres delimitadores (como espaços em branco, pontuações, etc) e dividir a string a cada ocorrência destes. Por exemplo, a frase "O rato roeu a roupa do rei de Roma." seria dividia em 9 tokens: "O", "rato", "roeu", "a", "roupa", "do", "rei", "de", "Roma".
A linguagem C oferece uma função para tokenização na biblioteca string.h,
denominada strtok(). Ela recebe como primeiro parâmetro um ponteiro para a
string a ser tokenizada, e como segundo parâmetro uma lista de delimitadores.
Ela retorna um ponteiro para o início do próximo token, ou NULL, caso não
existam mais tokens.
Esta função tem um comportamento incomum, devido três aspectos importantes:
- ela mantém, internamente, um ponteiro para o início do próximo token. Desta forma, para obter vários tokens de uma mesma string, as chamadas subsequentes à primeira devem receber
NULLcomo primeiro parâmetro (este comportamento faz com que esta função não seja segura num contexto multithread); - esta função altera o parâmetro de entrada, escrevendo o caractere
\0nas posições onde são encontrados delimitadores. Assim, se for necessário preservar o conteúdo original da string, deve ser passada uma cópia da mesma como primeiro parâmetro; - a função
strtok()não retorna tokens vazios (isto é, de tamanho zero).
O código abaixo ilustra o uso desta função para extrair os tokens de um CPF.
#include <stdio.h>
#include <string.h>
int main()
{
char cpf[] = "123.456.789-10";
char *token = NULL;
token = strtok(cpf, ".");
printf("token = [%s]\n", token); /* token = "123" */
token = strtok(NULL, ".");
printf("token = [%s]\n", token); /* token = "456" */
token = strtok(NULL, "-");
printf("token = [%s]\n", token); /* token = "798" */
token = strtok(NULL, "\0");
printf("token = [%s]\n", token); /* token = "10" */
printf("cpf = %s\n", cpf); /* cpf = "123" */
return 0;
}A mesma biblioteca oferece uma versão thread safe de strtok(), denominada
strtok_r(). Nesta versão, há um terceiro parâmetro, que é utilizado para
memorizar a posição do próximo token.
Em C++, a função getline() da biblioteca string pode ser utilizada para
tokenização. Ela recebe como primeiro parâmetro um fluxo de entrada (cin,
um arquivo, um fluxo de caracteres, etc), como segundo parâmetro a string
que conterá o token identificado e, como terceiro parâmetro, o caractere
delimitador (se omitido, o caractere \0 será considerado o delimitador).
Esta função é útil quando há apenas um delimitador e os tokens
são lidos diretamente da entrada.
O código de extração de tokens do CPF por ser reescrito em C++ da seguinte forma:
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
istringstream is("123.456.789-10");
string token;
getline(is, token, '.');
cout << token << endl; // token = "123";
getline(is, token, '.');
cout << token << endl; // token = "456";
getline(is, token, '-');
cout << token << endl; // token = "789";
getline(is, token);
cout << token << endl; // token = "10";
return 0;
}Para processos de tokenização mais elaborados pode ser necessário escrever um parser para tal. Os parsers serão discutidos mais adiante.
HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.
CROCHEMORE, Maxime; RYTTER, Wojciech. Jewels of Stringology: Text Algorithms, WSPC, 2002.
Inserir referências ao CPPreference (transform(), copy_if(), accumulate()).
WIKIPEDIA. Tokenization [https://en.wikipedia.org/wiki/Tokenization_(lexical_analysis)], Acesso em 22/01/17.