-
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['i'] = h['x'] = 1
h[c] = 0, c not in "abcix"
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;
}
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.
strtok();
HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.
CROCHEMORE, Maxime; RYTTER, Wojciech. Jewels of Stringology: Text Algorithms, WSPC, 2002.
REFERÊNCIA C REFERÊNCIA CPP REFERÊNCIA Python