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.

Um outro algoritmo de busca, baseado no uso de funções hash, é o algoritmo de Rabin Karp.

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

Algoritmo de Knuth-Morris-Pratt

O algoritmo de Morris-Pratt tem como invariante

    inv(i, j) = (pat[1..j] = text[i + 1, i + j + 1]),

que permite os saltos seguros e que leva a complexidade O(n + m). Contudo, este invariante pode ser melhorada, ao se incorporar a propriedade da diferença, isto é,

    inv2(i, j) = (pat[1..j] = text[i + 1, j + 1]) and (pat[j + 1] != text[i + j + 1]

Para entender o porque da melhora, considere o seguinte exemplo: seja pat = "abcabc" e text = "abcabdabc". Os 5 primeiros caracteres de ambos coincidem, e a diferença ocorre no sexto caractere: pat[5] = 'c' != text[5] = 'd'. Mas border[5] = 2 ("ab"), o que deslocaria a próxima comparação para pat[2] e text[5]. Contudo, esta comparação é idêntica a anterior, pois a borda "ab" não é própria, isto é, o próximo caractere ('c') gera uma nova borda "abc". A contribuição de Knuth para o algoritmo de Morris-Pratt é essa: incorporar a propriedade da diferença e definir as bordas estritas, onde o próximo caractere não gera uma nova borda.

Ao definirmos Strong_Bord[j] como o menor inteiro k que satisfaz a condição

    `cond(j, k) = (pat[1..k] é sufixo próprio de pat[1..j]) and
        (pat[k + 1] != pat[j + 1])

(ou -1, caso não exista tal inteiro) e

    KMP_Shift[j] = j - Strong_Bord[j],

a implementação do KMP é praticamente idêntica ao do MP:

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

    vector<int> bords = strong_borders(pat);

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

        if (j == m)
            ++occ;

        int KMP_shift = j - strong_bords[j];

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

    return occ;
}

Para o cálculo das bordas estritas basta observar que uma borda estrita é uma borda cujo próximo caractere do prefixo e do sufixo diferente. Caso estes caracteres sejam iguais, a borda estrita então deve ser avaliada novamente no prefixo encontrado.

Abaixo segue uma implementação em C++ para o cálculo das bordas estritas, que é uma variação do segundo algoritmo de bordas apresentado para o algoritmo de Morris-Pratt. Atente ao fato de que a primeira condição do if (isto é, j == m) subentende um caractere sentinela concatenado ao final do padrão.

vector<int>
strong_borders(const string& pat)
{
    int m = pat.size();
    int t = -1;

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

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

        ++t;

        if (j == m or pat[t] != pat[j])
            sbord[j] = t;
        else
            sbord[j] = sbord[t];
    }

    return sbord;
}

Referências

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

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