O algoritmo de Knuth-Morris-Pratt (KMP) resolve o problema clássico de busca de padrões em texto: dado um texto T de comprimento n e um padrão P de comprimento m, encontrar todas as ocorrências de P em T. Enquanto a abordagem ingênua (força bruta) pode degradar para O(n*m) no pior caso, o KMP garante tempo linear O(n+m) ao pré-processar o padrão para evitar comparações redundantes.
A ideia central é: quando ocorre um mismatch durante a comparação, já sabemos quais caracteres do texto correspondem parcialmente ao padrão. Usando essa informação (armazenada na tabela de falha), podemos pular posições no padrão sem precisar voltar no texto. Isso torna o KMP especialmente eficiente para textos longos e padrões com repetições internas.
Como Funciona
O KMP opera em duas fases: construção da tabela de falha (função prefixo) e busca propriamente dita.
Fase 1: Tabela de Falha (Failure Function)
A tabela de falha lps[i] armazena o comprimento do maior prefixo próprio do padrão P[0..i] que também é sufixo. Isso indica para onde o ponteiro do padrão deve “pular” após um mismatch.
Padrão: A B A B A C
Índice: 0 1 2 3 4 5
Construção passo a passo:
i=0: lps[0] = 0 (por definição)
i=1: P[1]='B' vs P[0]='A' -> mismatch -> lps[1] = 0
i=2: P[2]='A' vs P[0]='A' -> match -> lps[2] = 1
i=3: P[3]='B' vs P[1]='B' -> match -> lps[3] = 2
i=4: P[4]='A' vs P[2]='A' -> match -> lps[4] = 3
i=5: P[5]='C' vs P[3]='B' -> mismatch
len=lps[2]=1, P[5]='C' vs P[1]='B' -> mismatch
len=lps[0]=0, P[5]='C' vs P[0]='A' -> mismatch
lps[5] = 0
Resultado: lps = [0, 0, 1, 2, 3, 0]
Fase 2: Busca no Texto
Com a tabela pronta, percorremos o texto com um ponteiro i que nunca volta atrás. O ponteiro j do padrão avança quando há match e recua para lps[j-1] quando há mismatch.
Texto: A B A B A B A C
0 1 2 3 4 5 6 7
Padrão: A B A B A C
0 1 2 3 4 5
Passo 1: i=0 j=0 T[0]='A' == P[0]='A' -> match, i=1 j=1
Passo 2: i=1 j=1 T[1]='B' == P[1]='B' -> match, i=2 j=2
Passo 3: i=2 j=2 T[2]='A' == P[2]='A' -> match, i=3 j=3
Passo 4: i=3 j=3 T[3]='B' == P[3]='B' -> match, i=4 j=4
Passo 5: i=4 j=4 T[4]='A' == P[4]='A' -> match, i=5 j=5
Passo 6: i=5 j=5 T[5]='B' != P[5]='C' -> mismatch!
j = lps[4] = 3 (pula para posicao 3 do padrao)
(NAO volta no texto!)
Texto: A B A B A B A C
^
Padrão: A B [A B] A C
^ j=3
Passo 7: i=5 j=3 T[5]='B' == P[3]='B' -> match, i=6 j=4
Passo 8: i=6 j=4 T[6]='A' == P[4]='A' -> match, i=7 j=5
Passo 9: i=7 j=5 T[7]='C' == P[5]='C' -> match, j=6=m
>>> Padrao encontrado na posicao i-m = 7-6 = 2 <<<
Complexidade
| Caso | Tempo | Espaco |
|---|---|---|
| Melhor | O(n) | O(m) |
| Medio | O(n) | O(m) |
| Pior | O(n+m) | O(m) |
Onde n é o comprimento do texto e m é o comprimento do padrão. A fase de pré-processamento custa O(m) e a fase de busca custa O(n). Comparado com a abordagem ingênua O(n*m), o KMP é significativamente melhor para padrões com repetições internas e textos longos.
Implementacao em Rust
/// Constroi a tabela de falha (LPS - Longest Proper Prefix which is also Suffix)
/// para o padrao fornecido.
fn construir_tabela_falha(padrao: &[u8]) -> Vec<usize> {
let m = padrao.len();
let mut lps = vec![0usize; m];
let mut comprimento = 0; // comprimento do prefixo/sufixo anterior
let mut i = 1;
while i < m {
if padrao[i] == padrao[comprimento] {
comprimento += 1;
lps[i] = comprimento;
i += 1;
} else if comprimento != 0 {
// Nao incrementa i; tenta o proximo candidato
comprimento = lps[comprimento - 1];
} else {
lps[i] = 0;
i += 1;
}
}
lps
}
/// Busca todas as ocorrencias do padrao no texto usando o algoritmo KMP.
/// Retorna um vetor com as posicoes iniciais de cada ocorrencia.
fn kmp_busca(texto: &str, padrao: &str) -> Vec<usize> {
let texto = texto.as_bytes();
let padrao = padrao.as_bytes();
let n = texto.len();
let m = padrao.len();
if m == 0 || m > n {
return Vec::new();
}
let lps = construir_tabela_falha(padrao);
let mut ocorrencias = Vec::new();
let mut i = 0; // indice no texto
let mut j = 0; // indice no padrao
while i < n {
if texto[i] == padrao[j] {
i += 1;
j += 1;
}
if j == m {
// Padrao encontrado na posicao i - j
ocorrencias.push(i - j);
j = lps[j - 1]; // continua buscando proxima ocorrencia
} else if i < n && texto[i] != padrao[j] {
if j != 0 {
j = lps[j - 1]; // usa tabela de falha
} else {
i += 1;
}
}
}
ocorrencias
}
fn main() {
let texto = "ABABABABAC";
let padrao = "ABABAC";
println!("Texto: \"{}\"", texto);
println!("Padrao: \"{}\"", padrao);
println!();
// Mostra a tabela de falha
let lps = construir_tabela_falha(padrao.as_bytes());
println!("Tabela de falha (LPS):");
for (i, ch) in padrao.chars().enumerate() {
println!(" lps[{}] = {} (caractere '{}')", i, lps[i], ch);
}
println!();
// Executa a busca
let resultados = kmp_busca(texto, padrao);
if resultados.is_empty() {
println!("Padrao nao encontrado no texto.");
} else {
println!("Padrao encontrado em {} posicao(oes):", resultados.len());
for pos in &resultados {
println!(" Posicao {}: \"{}\"", pos, &texto[*pos..*pos + padrao.len()]);
}
}
}
Exemplo de Execucao
Texto: "ABABABABAC"
Padrao: "ABABAC"
Tabela de falha (LPS):
lps[0] = 0 (caractere 'A')
lps[1] = 0 (caractere 'B')
lps[2] = 1 (caractere 'A')
lps[3] = 2 (caractere 'B')
lps[4] = 3 (caractere 'A')
lps[5] = 0 (caractere 'C')
Padrao encontrado em 1 posicao(oes):
Posicao 4: "ABABAC"
Trace visual detalhado:
Texto: A B A B A B A B A C
Padrao: A B A B A C
^ ^ mismatch em i=5, j=5
j pula para lps[4]=3
Texto: A B A B A B A B A C
Padrao: A B A B A C
^ continua de j=3, i=5
^ mismatch em i=5, j=3? Nao: B==B, match!
Texto: A B A B A B A B A C
Padrao: A B A B A C
^ ^ ^ mismatch em i=7, j=5
j pula para lps[4]=3
Texto: A B A B A B A B A C
Padrao: A B A B A C
^ continua de j=3, i=7
B==B, A==A, C==C -> match completo!
>>> Encontrado na posicao 4 <<<
Variacoes e Otimizacoes
1. Contagem de Ocorrencias sem Armazenamento
Quando voce precisa apenas contar quantas vezes o padrao aparece, sem guardar as posicoes:
/// Conta o numero de ocorrencias do padrao no texto.
fn kmp_contar(texto: &str, padrao: &str) -> usize {
let texto = texto.as_bytes();
let padrao = padrao.as_bytes();
let n = texto.len();
let m = padrao.len();
if m == 0 || m > n {
return 0;
}
let lps = construir_tabela_falha(padrao);
let mut contagem = 0;
let mut i = 0;
let mut j = 0;
while i < n {
if texto[i] == padrao[j] {
i += 1;
j += 1;
}
if j == m {
contagem += 1;
j = lps[j - 1];
} else if i < n && texto[i] != padrao[j] {
if j != 0 {
j = lps[j - 1];
} else {
i += 1;
}
}
}
contagem
}
2. KMP com Busca Case-Insensitive
/// Busca KMP ignorando maiusculas/minusculas (apenas ASCII).
fn kmp_busca_case_insensitive(texto: &str, padrao: &str) -> Vec<usize> {
let texto_lower: Vec<u8> = texto.bytes().map(|b| b.to_ascii_lowercase()).collect();
let padrao_lower: Vec<u8> = padrao.bytes().map(|b| b.to_ascii_lowercase()).collect();
let n = texto_lower.len();
let m = padrao_lower.len();
if m == 0 || m > n {
return Vec::new();
}
let lps = construir_tabela_falha(&padrao_lower);
let mut ocorrencias = Vec::new();
let mut i = 0;
let mut j = 0;
while i < n {
if texto_lower[i] == padrao_lower[j] {
i += 1;
j += 1;
}
if j == m {
ocorrencias.push(i - j);
j = lps[j - 1];
} else if i < n && texto_lower[i] != padrao_lower[j] {
if j != 0 {
j = lps[j - 1];
} else {
i += 1;
}
}
}
ocorrencias
}
3. Primeira Ocorrencia (Early Return)
Para quando voce so precisa saber se o padrao existe e onde aparece pela primeira vez:
/// Retorna a posicao da primeira ocorrencia, ou None se nao encontrado.
fn kmp_primeira_ocorrencia(texto: &str, padrao: &str) -> Option<usize> {
let texto = texto.as_bytes();
let padrao = padrao.as_bytes();
let n = texto.len();
let m = padrao.len();
if m == 0 || m > n {
return None;
}
let lps = construir_tabela_falha(padrao);
let mut i = 0;
let mut j = 0;
while i < n {
if texto[i] == padrao[j] {
i += 1;
j += 1;
}
if j == m {
return Some(i - j); // retorna imediatamente
} else if i < n && texto[i] != padrao[j] {
if j != 0 {
j = lps[j - 1];
} else {
i += 1;
}
}
}
None
}
Aplicacoes Praticas
Busca em Logs
/// Busca um padrao em multiplas linhas de log e retorna as linhas correspondentes.
fn buscar_em_logs(logs: &[&str], padrao: &str) -> Vec<(usize, String)> {
let mut resultados = Vec::new();
for (num_linha, linha) in logs.iter().enumerate() {
let ocorrencias = kmp_busca(linha, padrao);
if !ocorrencias.is_empty() {
resultados.push((num_linha + 1, linha.to_string()));
}
}
resultados
}
fn main() {
let logs = vec![
"2026-02-24 INFO: Servidor iniciado na porta 8080",
"2026-02-24 ERROR: Falha na conexao com banco de dados",
"2026-02-24 INFO: Reconectando ao banco de dados",
"2026-02-24 ERROR: Timeout na conexao - banco de dados indisponivel",
"2026-02-24 INFO: Conexao restabelecida com sucesso",
];
let resultados = buscar_em_logs(&logs, "ERROR");
println!("Linhas com ERROR:");
for (num, linha) in &resultados {
println!(" Linha {}: {}", num, linha);
}
}
Detector de Repeticoes em Texto
/// Verifica se uma string e formada pela repeticao de um padrao.
/// Usa a propriedade do KMP: se n % (n - lps[n-1]) == 0, a string
/// e uma repeticao do prefixo de comprimento (n - lps[n-1]).
fn detectar_repeticao(texto: &str) -> Option<String> {
let bytes = texto.as_bytes();
let n = bytes.len();
if n == 0 {
return None;
}
let lps = construir_tabela_falha(bytes);
let tamanho_padrao = n - lps[n - 1];
if tamanho_padrao < n && n % tamanho_padrao == 0 {
Some(texto[..tamanho_padrao].to_string())
} else {
None
}
}
fn main() {
let exemplos = ["abcabcabc", "ababab", "abcdef", "aaaa"];
for s in &exemplos {
match detectar_repeticao(s) {
Some(padrao) => println!("\"{}\" = repeticao de \"{}\"", s, padrao),
None => println!("\"{}\" nao e uma repeticao", s),
}
}
}
Comparacao com Outros Algoritmos
| Algoritmo | Pre-proc. | Busca | Espaco | Multiplos padroes |
|---|---|---|---|---|
| Forca Bruta | O(0) | O(n*m) | O(1) | Nao |
| KMP | O(m) | O(n) | O(m) | Nao |
| Rabin-Karp | O(m) | O(n+m)* | O(1) | Sim |
| Boyer-Moore | O(m+k) | O(n/m)+ | O(k) | Nao |
| Aho-Corasick | O(soma m) | O(n+z) | O(soma m) | Sim |
* Medio; pior caso O(n*m). + Melhor caso; k = tamanho do alfabeto; z = numero de matches.
O KMP brilha quando voce precisa de garantia de pior caso linear para busca de um unico padrao. Para multiplos padroes simultaneos, considere Aho-Corasick. Para textos onde o padrao raramente aparece, Boyer-Moore pode ser mais rapido na pratica.
Exercicios Praticos
Busca circular: Dado um texto circular (o final conecta ao inicio), encontre todas as ocorrencias do padrao. Dica: concatene o texto consigo mesmo e use KMP, filtrando posicoes >= n.
Menor periodo: Dada uma string, encontre o menor periodo (menor prefixo que, repetido, forma a string ou um prefixo dela). Use a tabela LPS.
KMP em stream: Modifique o KMP para processar caracteres um a um (como se viessem de um stream), mantendo o estado entre chamadas. Implemente como uma struct com metodo
alimentar(byte: u8) -> bool.Contagem de prefixos: Dada uma string S, para cada posicao i, calcule quantas vezes o prefixo S[0..i] aparece em S. Use a tabela LPS de forma criativa.
Veja Tambem
- String na Biblioteca Padrao – manipulacao de strings em Rust
- Vec: Vetores Dinamicos – o tipo Vec
usado na tabela de falha - Slices em Rust – fatias para processamento eficiente de bytes
- Projeto: Motor de Regex – construa um motor de expressoes regulares
- Algoritmo Rabin-Karp – busca com hashing
- Algoritmo Aho-Corasick – busca de multiplos padroes