← Algoritmos

Busca de Substring: Da Força Bruta ao Knuth-Morris-Pratt

Published on 2026-08-13·v1.0

Objetivo

Entenda a busca de substring: encontrar um padrão de comprimento M dentro de um texto de comprimento N. Comece pela abordagem óbvia de força bruta e seu pior caso O(NM), depois veja a percepção — um mismatch já diz algo sobre o texto que você acabou de varrer — que o Knuth-Morris-Pratt (KMP) transforma num pequeno autômato construído uma vez a partir do padrão, permitindo varrer o texto exatamente uma vez, da esquerda para a direita, sem retroceder, em O(N) depois do pré-processamento.

Casos de Uso

  • A funcionalidade "buscar" de um editor de texto ou navegador, ou uma busca estilo grep por uma string fixa dentro de um log ou documento grande.
  • Varrer um fluxo de entrada que você não pode rebobinar — tráfego de rede, stdin, uma mensagem interceptada — onde um algoritmo que nunca retrocede o ponteiro do texto evita ter que armazenar em buffer caracteres já consumidos.
  • Detecção de assinatura/padrão contra um corpo de texto longo e fixo (uma frase importante numa comunicação interceptada, uma string marcadora conhecida num blob binário grande) onde o mesmo padrão curto é buscado repetidamente.

Aprofundamento

Busca de substring por força bruta e seu pior caso

O algoritmo óbvio: para toda posição inicial i possível no texto, verifique se o padrão bate caractere por caractere, parando no primeiro mismatch.

java
public static int search(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();
    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (txt.charAt(i + j) != pat.charAt(j)) break;
        if (j == M) return i; // encontrado
    }
    return N; // não encontrado
}

Sedgewick e Wayne também dão uma versão de "retrocesso explícito" que mantém um único índice i no texto (rastreando i + j da versão acima) e um segundo índice j no padrão, incrementando os dois juntos numa correspondência e resetando num mismatch. Nomear o reset explicitamente é o que importa aqui — é exatamente a operação que o KMP foi feito para evitar:

java
public static int search(String pat, String txt) {
    int M = pat.length(), N = txt.length();
    int i, j;
    for (i = 0, j = 0; i < N && j < M; i++) {
        if (txt.charAt(i) == pat.charAt(j)) j++;
        else { i -= j; j = 0; } // retrocede: tenta de novo começando uma posição depois
    }
    if (j == M) return i - M; // encontrado
    else return N;            // não encontrado
}

Em texto típico isso é rápido — quase todo mismatch acontece já no primeiro caractere do padrão, então o tempo de execução fica próximo de N. Mas o pior caso é genuinamente O(NM): faça padrão e texto serem sequências do mesmo caractere repetido seguidas por um caractere diferente. Pegue o padrão "AAAB" (M = 4) contra o texto "AAAAAAAAAAAAAAAB" (quinze As seguidos de um B, N = 16). Em toda posição inicial i de 0 a 11, os três primeiros caracteres batem ("AAA" contra "AAA"), e só a quarta comparação — o 'B' do padrão contra o 'A' do texto — falha. Quase o padrão inteiro é recomparado em cada uma das doze posições iniciais que falham antes de a correspondência finalmente ser encontrada em i = 12. A Proposição M de Sedgewick e Wayne declara o resultado geral: a busca por força bruta exige ~NM comparações de caractere no pior caso.

A percepção central do KMP: um mismatch já te diz algo

O i -= j; j = 0; da força bruta joga fora informação de graça: no momento de um mismatch, os j caracteres anteriores do texto já são conhecidos — são exatamente os primeiros j caracteres do padrão, porque isso é o que acabou de bater. A ideia fundadora do KMP é que esse texto já conhecido pode descartar algumas das próximas posições iniciais antes mesmo de olhar para elas, de forma que o ponteiro do texto nunca precise se mover para trás.

A própria ilustração de Sedgewick e Wayne: busque o padrão "BAAAAAAAAA" (um B seguido de nove As) sobre um alfabeto de dois caracteres, e suponha que cinco caracteres batam antes de um mismatch no sexto. Nesse ponto sabe-se que o texto lê "BAAAAB" no ponto do mismatch (cinco As bateram, depois um B onde o padrão esperava um A). A força bruta retrocederia o ponteiro do texto quatro vezes, tentando de novo posições iniciais que só contêm mais daqueles As já conhecidos — nenhum dos quais pode possivelmente bater com o B inicial do padrão. O caractere que de fato está sentado na posição do mismatch, porém, é um B — exatamente o primeiro caractere do padrão. Então em vez de retroceder o ponteiro do texto de forma alguma, o conserto é simplesmente resetar j para 1 (não 0) e continuar movendo i para frente. Sem retrocesso, e a busca ainda termina corretamente.

Aquele atalho específico — pular direto para bater com o primeiro caractere do padrão — não generaliza para todo padrão, porque um padrão pode se sobrepor consigo mesmo. Buscar "AABAAA" em "AABAABAAAA" bate um mismatch na posição 5, mas o ponto de reinício correto é a posição 3, não mais à frente: pular além da posição 3 perderia uma correspondência real. A generalização que o KMP faz é que exatamente até onde é seguro pular — e para qual posição do padrão retomar — depende só do padrão em si, e por isso pode ser calculado uma vez, com antecedência, antes de o texto ser sequer varrido.

Construindo o DFA: pré-computa uma vez, varre o texto uma vez sem retroceder

O KMP transforma o padrão num pequeno autômato finito determinístico (DFA): um estado por caractere do padrão (mais um estado final "encontrado" M), onde o número do estado é o índice j do padrão sendo comparado no momento. Ler um caractere do texto no estado j consulta uma tabela de transição dfa[c][j] — o estado para o qual ir a seguir — e avança o ponteiro do texto em exatamente um, sempre, seja essa consulta uma correspondência ou um mismatch. dfa[pat.charAt(j)][j] é sempre j + 1 (uma correspondência avança um estado); todo outro caractere faz dfa[c][j] apontar para algum estado ≤ j, pré-computado para refletir exatamente quanto do prefixo do padrão os caracteres de texto já conhecidos satisfazem.

java
public class KMP {
    private final String pat;
    private final int[][] dfa;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        int R = 256;
        dfa = new int[R][M];
        dfa[pat.charAt(0)][0] = 1;
        for (int X = 0, j = 1; j < M; j++) {
            for (int c = 0; c < R; c++)
                dfa[c][j] = dfa[c][X];      // copia os casos de mismatch do estado de reinício X
            dfa[pat.charAt(j)][j] = j + 1;  // define o caso de correspondência
            X = dfa[pat.charAt(j)][X];      // atualiza o estado de reinício
        }
    }

    public int search(String txt) {
        int i, j, N = txt.length(), M = pat.length();
        for (i = 0, j = 0; i < N && j < M; i++)
            j = dfa[txt.charAt(i)][j];
        if (j == M) return i - M; // encontrado
        else return N;            // não encontrado
    }
}

A construção é a parte sutil. Cada estado X rastreado durante a construção é o estado em que o DFA cairia se um mismatch acontecesse bem na coluna j e a busca precisasse reiniciar — o truque é que X só depende das posições do padrão antes de j, que já foram construídas, então dfa[c][j] pode simplesmente copiar dfa[c][X] para todo caractere c de mismatch, e então sobrescrever o único caractere de correspondência com j + 1. Para o padrão "ABABAC", isso produz:

plaintext
j:              0   1   2   3   4   5
pat.charAt(j):  A   B   A   B   A   C
dfa['A'][j]:    1   1   3   1   5   1
dfa['B'][j]:    0   2   0   4   0   4
dfa['C'][j]:    0   0   0   0   0   6

Uma vez que dfa[][] está construído, search() nunca mais inspeciona i - 1 — ele lê cada caractere do texto exatamente uma vez e move j dentro da tabela. Proposição N de Sedgewick e Wayne: o KMP acessa no máximo M + N caracteres no total para buscar um padrão de comprimento M num texto de comprimento N — O(M) para acessar cada caractere do padrão ao construir o DFA, e O(N) para varrer o texto uma vez, uma garantia real de pior caso, não uma de caso médio. O custo de construir a própria tabela é O(MR), onde R é o tamanho do alfabeto, já que cada uma das M colunas copia R entradas.

Trade-offs

  • A força bruta é simples, amigável ao cache, e tipicamente ~1.1N comparações — mas O(NM) em entrada adversarial ou auto-repetitiva (sequências longas de um caractere repetido tanto no padrão quanto no texto, como mostrado acima). Não é só um brinquedo de livro-texto: Sedgewick e Wayne observam que o próprio String.indexOf() do Java usa busca por força bruta, porque o caso comum é rápido o suficiente para que a contabilidade extra que KMP ou Boyer-Moore exigem raramente se pague em código de biblioteca de propósito geral.
  • O KMP troca tempo e espaço de pré-processamento por uma garantia de pior caso. O DFA completo custa O(MR) de tempo e espaço para construir (uma tabela de M colunas e R linhas), o que é memória extra real que a força bruta nunca precisa — e na prática o ganho de velocidade sobre a força bruta raramente importa, porque poucas aplicações reais buscam um padrão altamente auto-repetitivo num texto altamente auto-repetitivo. O que o KMP garante incondicionalmente é que o ponteiro do texto nunca se move para trás, o que importa muito mais que o ganho bruto de velocidade sempre que a entrada é um stream que não pode ser rebobinado.
  • O Boyer-Moore varre o padrão da direita para a esquerda e costuma ser mais rápido na prática, mas com um pior caso diferente. Sua heurística de caractere com mismatch usa uma tabela right[] — para cada caractere, sua posição mais à direita no padrão — para às vezes pular várias posições de texto de uma vez num único mismatch, em vez de avançar de uma em uma. Em texto típico parecido com inglês isso dá ~N/M comparações de caractere, sublinear no comprimento do padrão, motivo pelo qual muitos editores de texto usam Boyer-Moore. Mas a versão simples da heurística de caractere com mismatch (diferente do KMP) não tem garantia linear de pior caso — Sedgewick e Wayne observam que ela ainda pode levar tempo proporcional a NM; só o algoritmo Boyer-Moore completo, que adiciona uma tabela estilo KMP para as auto-sobreposições do padrão, restaura uma garantia de tempo linear.

Documentation Links