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

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).

Histograma

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

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;
}

Tabelas de substituição

Tokenização

strtok();

Anagramas

Parsing

Expressões Regulares

Referências

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