Algoritmos de Busca

A busca é o algoritmo fundamental dentre os algoritmos de strings e, conforme dito anteriormente, se equivalente, em importância, aos algoritmos de ordenação no estudo de algoritmos.

A busca em strings consiste em determinar se uma string pat, de tamanho m, ocorre ou não em uma string text, de tamanho n (ou o número de tais ocorrências).

Os principais algoritmos de busca em strings são: a busca completa, o algoritmo de Knuth-Morris-Pratt (KMP) e o algoritmo de Boyer-Moore (BM). O primeiro deles é de fácil entendimento e codificação; os dois últimos são conceitualmente divididos em duas etapas:

1. pré-processamento do padrão, que envolve a construção de certas tabelas;
2. busca, onde se determina a primeira (ou todas) ocorrência(s) de pat em text.

Busca Completa

A busca completa compara cada uma das n - m + 1 substrings de tamanho m de text com pat, reportando cada igualdade. Como a comparação tem complexidade O(m) e o número de substrings é O(n), temos um algoritmo com complexidade quadrática O(mn).

Uma possível implementação em C++ é ilustrada abaixo.

int occurrences(const string& text, const string& pat)
{
    int n = text.size();
    int m = pat.size();

    int occ = 0;    // Número de ocorrências de pat em text

    for (int i = 0; i <= n - m; ++i) 
        occ += (pat == text.substr(i, m) ? 1 : 0);

    return occ;
}

O único cuidado a ser tomado, na implementação, é se certificar que todas as substrings foram verificadas (atentar para o <= na condição do laço).

Outro ponto importante a se notar é que a comparação entre pat e a subtring pode ser feita tanto da esquerda para direita quanto em sentido oposto, e estas duas alternativas constituem as ideias fundamentais para os outros dois algoritmos: KMP e BM.

Algoritmo de Morris-Pratt

Na função occurrences() descrita acima, as comparações feitas entre a substring em questão e o padrão são independentes, o que resulta em várias comparações sendo feitas mais de uma vez e desnecessáriamente.

Por exemplo, considere text = "xyzabcdfgh" e pat = "abcde". A comparação entre a substring com início no índice 3 (a saber, abcdf) e o padrão falha no último caractere ('f' != 'e'), localizado no índice 7. Como todos os caracteres do padrão são distintos, é possível identificar que o padrão não pode ocorrer nos índices de 4 a 6, mas occurrences() ainda assim realiza tais comparações.

O algoritmo de Morris-Pratt explora justamente as comparações entre caracteres já feitas, movendo o índice de ínicio das comparações entre as substrings e o padrão para a posição mais distante o possível. Para melhor explicar o funcionamento de tal algoritmo, precisamos de algumas definições preliminares.

Chamamos salto seguro s ao inteiro positivo tal que há garantias de que o padrão não pode acontecer entre as posições i e i + s do texto, mas que pode-se iniciar o padrão em i+s.

Quando o padrão contém caracteres distintos, é seguro saltar para a posição onde aconteceu a falha. Contudo, devemos ter cuidado quando há repetições de letras no padrão. Mais precisamente, para que o salto seja seguro, devemos identificar a maior borda possível para pat[1..j]: devemos saltar para a posição onde a borda se inicia. Assim, o salto seguro de Morris-Pratt para o padrão pat[1..j], j = 1, 2, ..., m é dado por

    MP_shift[j] = j - |border(pat[1..j])|

Lembre-se de que border(s) é a maior substring x de s que é, ao mesmo tempo, sufixo e prefixo de s. No caso especial de uma string vazio, o salto deve assumir o valor mínimo de 1, de modo que devemos fazer MP_shift[0] = 1.

De posse do vetor MP_shift, temos uma possível implementação do algoritmo de Morris-Pratt.

int MP(const string& text, const string& pat)
{
    int n = text.size();
    int m = pat.size();
    int i = 0, j = 0, occ = 0;

    while (i <= n + m)
    {
        while (j < m and pat[j] == text[i + j])
            ++j;

        if (j == m)
            ++occ;

        i += MP_shift[j];
        j = max(0, j - MP_shift[j]);
    } 

    return occ;
}

Referências

HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.

CROCHEMORE, Maxime; RYTTER, Wojciech. Jewels of Stringology: Text Algorithms, WSPC, 2002.