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 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 a partir dos í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 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 esta 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 vazia, 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;

    vector<int> bords = borders(pat);

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

        if (j == m)
            ++occ;

        int MP_shift = j - bords[j];

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

    return occ;
}

O algoritmo de Morris-Pratt realiza, no máximo, um número de comparações linear em termos dos tamanhos de text e pat, a saber, 2n - m comparações. Isto pode ser observado da seguinte maneira: serão feitas, no máximo, a comparação pat[j] == text[i + j] pode falhar, no máximo, n - m + 1 vezes (o primeiro laço é executado n - m + 1 vezes) e pode ter sucesso, no máximo, n vezes (quando o padrão e o texto são idênticos). Caso a primeira comparação seja bem sucedida, ela não pode falhar no índice 0. Daí o máximo de comparações será igual a n + (n - m) = 2n - m.

Assim, o algoritmo MP é linear em relação ao tamanho do texto. Porém, para determinar sua complexidade, falta determinar a complexidade da construção do vetor MP_shift. Este vetor pode ser construído a partir de uma variação do próprio MP, de modo que teremos uma construção também linear em relação ao tamanho do texto. Daí, a complexidade do algoritmo MP é O(n).

Para construir MP_shift, determinaremos os valores de border(pat[1..j]) a partir de uma variante do algoritmo MP, onde text == pat, apresentada a seguir.

// Computa o tamanho das bordas de pat: bord[j] é o tamanho da borda da
// substring pat[0..(j-1)]
vector<int>
borders(const string& pat)
{
    int m = pat.size();
    int i = 1, j = 0;

    vector<int> bord(m + 1, -1);    // Inicialmente, bord[j] = -1 para todo j

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

            if (bord[i + j] == -1)
                bord[i + j] = j;
        }

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

    // Ajuste para compatibilidade entre os dois algoritmos de borda
    for (int i = 1; i <= m; ++i)
        if (bord[i] == -1)
            bord[i] = 0;

    return bord;
}

Vale notar que, no momento das atualizações de i e j, ao final do primeiro laço, os valores de bord[j] já estão devidamente computados, e que i inicia em 1, não em zero (bord[0] = -1: uma string de tamanho 1 não tem bordas não triviais e o valor -1 faz com que a atualização de i seja igual a, no mínimo, um).

Contudo, o algoritmo mais comum para o cálculo das bordas é apresentado abaixo. Assim como a variação do MP, também é linear em relação ao tamanho de pat.

// Computa o tamanho das bordas de pat: bord[j] é o tamanho da borda da
// substring pat[0..(j-1)]
vector<int> borders2(const string& pat)
{
    int m = pat.size();
    int t = -1;

    vector<int> bord(m + 1);
    bord[0] = -1;

    for (int j = 1; j <= m; ++j)
    {
        while (t >= 0 and pat[t] != pat[j - 1])
            t = bord[t];

        ++t;
        bord[j] = t;
    }

    return bord;
}

Referências

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

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