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,

Referências

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

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