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

Conversões para/de inteiros

Mapas, Filtros e Reduções

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