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

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