Correspondência Exata de Strings

Dados um texto de comprimento n e um padrão de comprimento m, a correspondência exata informa todas as posições em que o padrão ocorre sem divergências.

Busca ingênua

Teste cada alinhamento e compare símbolos até encontrar uma divergência. O tempo no pior caso é O((n - m + 1)m), ou O(nm), e o espaço auxiliar é O(1). Essa abordagem costuma ser adequada para padrões curtos ou entradas pequenas.

Knuth–Morris–Pratt

O KMP pré-processa o padrão em uma tabela do maior prefixo próprio que também é sufixo. Após uma divergência, a tabela identifica quanto da estrutura já encontrada pode ser reutilizado sem retroceder o índice do texto.

O pré-processamento custa Θ(m), e a busca custa Θ(n), totalizando tempo Θ(n + m) e espaço auxiliar Θ(m). A correção decorre do invariante de prefixo: o prefixo atualmente encontrado também é um sufixo do texto processado até então, e a transição de falha escolhe o maior prefixo menor que ainda pode corresponder.

Rabin–Karp

O Rabin–Karp compara hashes incrementais de cada janela e então verifica os caracteres quando os hashes coincidem. Com um modelo de hash adequado, o tempo esperado é O(n + m), mas colisões podem produzir O(nm) de trabalho de verificação. Nunca trate a igualdade de hashes como prova da igualdade de strings, salvo quando a aplicação aceitar erro probabilístico.

Família Boyer–Moore

A comparação da direita para a esquerda, combinada com deslocamentos por caractere ruim e sufixo bom, pode saltar grandes regiões e funciona bem em muitos textos práticos. As variantes possuem pré-processamentos e garantias de pior caso diferentes; portanto, identifique a variante exata ao declarar um limite.

Considerações em Java

Índices de String referenciam unidades de código UTF-16. Buscar caracteres conforme percebidos por seres humanos pode exigir iteração por pontos de código, normalização ou uma biblioteca de texto. Para a busca comum de substrings, prefira a API padrão testada, exceto quando estiver estudando ou precisar de um algoritmo especializado de correspondência.

Exercícios

1. Construa a tabela de prefixos do KMP para ABABACA.
2. Construa um pior caso para a busca ingênua.
3. Explique por que correspondências de hashes incrementais precisam ser verificadas.