Contador de passos de busca KMP | Tabela de falhas e economia de passos à vista

Veja o algoritmo Knuth-Morris-Pratt trabalhar no seu próprio texto. Esta ferramenta constrói a tabela da função de falha LPS do seu padrão, executa a varredura KMP em tempo linear e conta quantas comparações de caracteres o KMP precisa em comparação a uma busca ingênua de laço duplo sobre a mesma entrada.

💡 Sobre esta ferramenta

A maioria das explicações de KMP para em "é O(n+m), confie". Isso deixa uma lacuna: dá para recitar o limite de complexidade sem sentir de onde vem a economia, nem por que a função de falha importa. E na hora de implementar KMP num exercício ou numa entrevista, a tabela LPS é justamente a parte que derruba a maioria.

Este contador fecha essa lacuna com números concretos da sua entrada. Digite qualquer padrão e texto, e você vê o vetor LPS linha a linha (i, p[i], lps[i]), as posições exatas de correspondência e a contagem de comparações lado a lado. Como os números de KMP e da busca ingênua saem do mesmo texto, você acha o ponto de equilíbrio sozinho: em texto aleatório a diferença é pequena, mas com um padrão como aaaab contra uma longa sequência de a, a busca ingênua dispara enquanto o KMP permanece linear. Esse contraste é o cerne do algoritmo, e aqui você o reproduz quando quiser.

🧐 Perguntas frequentes

O que a tabela LPS realmente guarda? LPS[i] é o comprimento do maior prefixo próprio de p[0..i] que também é sufixo de p[0..i]. Em uma divergência, o KMP move o ponteiro do padrão para LPS[j-1] em vez de reiniciar do zero, e é isso que elimina as comparações redundantes.

Como uma "comparação" é contada aqui? Um passo equivale a uma comparação entre um caractere do padrão e um caractere do texto. Os recuos de ponteiro que o KMP faz pela tabela LPS não contam como passos, pois não tocam nenhum caractere do texto. A busca ingênua conta cada comparação do laço interno.

Por que a aceleração às vezes mal passa de 1x? Em texto natural ou aleatório, as divergências costumam ocorrer no primeiro caractere, então a busca ingênua raramente recua muito. A vantagem do KMP aparece com padrões de prefixos repetidos longos contra texto adversário, onde a busca ingênua reexamina os mesmos caracteres várias vezes.

Ele detecta correspondências sobrepostas? Sim. Após uma correspondência completa, o KMP reinicia j para LPS[m-1], então ocorrências sobrepostas (como aa dentro de aaaa) são todas reportadas. Os índices são base 0.

Espaços e símbolos contam? Sim. A busca é por caractere, então espaços, quebras de linha e pontuação são comparados literalmente. Não há limite de comprimento em nenhum campo, embora padrões mais curtos construam sua tabela LPS mais rápido.

📚 Curiosidades

O KMP foi publicado em 1977 por Donald Knuth, James Morris e Vaughan Pratt. Antes dele, o padrão era a busca ingênua, cujo pior caso é O(n·m): basta um padrão quase-todo-igual contra um texto quase-todo-igual para o número de comparações crescer de forma quadrática. A função de falha é, no fundo, um pequeno autômato finito compilado a partir do padrão. A mesma ideia de função prefixo reaparece longe da busca de cadeias: sustenta truques de programação competitiva como contar as bordas distintas de uma string ou achar o menor período de uma sequência repetida.