🧩 Algoritmo KMP (Knuth-Morris-Pratt) em PHP

O Knuth-Morris-Pratt (KMP) é um algoritmo clássico de busca de string que melhora a eficiência evitando comparações desnecessárias. Ele utiliza o conhecimento prévio sobre o padrão sendo buscado para pular caracteres no texto, garantindo que nunca precisemos voltar atrás (backtracking) no ponteiro do texto.

💡 Por que e Quando Usar?

O KMP brilha onde a consistência e a garantia de pior caso linear são necessárias.

💻 Aplicabilidade Prática

Busca em Sistemas de Cache/Memória (Simulação de In-Memory Search)

Cenário: Em vez de fazer uma busca em um banco de dados, a string é buscada em um array grande na memória (por exemplo, um cache de URLs ou tokens). Vantagem do KMP: Se o padrão de busca for repetitivo ou tiver muitos prefixos que se repetem (como "AAAAAB"), o KMP é ideal porque minimiza o backtracking, mantendo a performance estável.

Processamento de Streams

Cenário: Ler dados de um stream contínuo onde não é possível "voltar" para ler caracteres anteriores. Vantagem do KMP: Como o KMP avança linearmente pelo texto sem nunca retroceder o índice do texto, ele é perfeito para processar streams de dados em tempo real.

🚀 Implementação em PHP

A implementação do KMP envolve duas partes:

1. Pré-processamento (Tabela LPS): Criar a tabela "Longest Prefix Suffix" que diz para onde pular quando ocorre um mismatch.
2. Busca: Usar a tabela LPS para navegar pelo texto.

<?php

class KMP {
    /**
     * Calcula a tabela LPS (Longest Prefix Suffix).
     * 
     * @param string $pattern
     * @return array
     */
    private function computeLPSArray(string $pattern): array {
        $m = strlen($pattern);
        $lps = array_fill(0, $m, 0);
        $len = 0; // Comprimento do prefixo anterior mais longo
        $i = 1;

        while ($i < $m) {
            if ($pattern[$i] == $pattern[$len]) {
                $len++;
                $lps[$i] = $len;
                $i++;
            } else {
                if ($len != 0) {
                    $len = $lps[$len - 1];
                } else {
                    $lps[$i] = 0;
                    $i++;
                }
            }
        }
        return $lps;
    }

    /**
     * Busca todas as ocorrências de um padrão em um texto usando KMP.
     *
     * @param string $pattern O padrão a ser buscado
     * @param string $text O texto onde buscar
     * @return array Lista de índices onde o padrão foi encontrado
     */
    public function search(string $pattern, string $text): array {
        $m = strlen($pattern);
        $n = strlen($text);

        if ($m == 0) return [];
        if ($m > $n) return [];

        $lps = $this->computeLPSArray($pattern);
        $i = 0; // índice para text
        $j = 0; // índice para pattern
        $occurrences = [];

        while ($i < $n) {
            if ($pattern[$j] == $text[$i]) {
                $j++;
                $i++;
            }

            if ($j == $m) {
                $occurrences[] = $i - $j;
                $j = $lps[$j - 1];
            } elseif ($i < $n && $pattern[$j] != $text[$i]) {
                if ($j != 0) {
                    $j = $lps[$j - 1];
                } else {
                    $i++;
                }
            }
        }

        return $occurrences;
    }
}

// --- Testes e Exemplos ---

$kmp = new KMP();

// Exemplo 1: Padrão com repetições
$texto = "ABABDABACDABABCABAB";
$padrao = "ABABCABAB";
$resultado = $kmp->search($padrao, $texto);
echo "Padrão encontrado nos índices: " . implode(", ", $resultado) . "\n";

// Exemplo 2: Texto com muitas repetições parciais
$texto2 = "AAAAABAAABA";
$padrao2 = "AAAA";
$resultado2 = $kmp->search($padrao2, $texto2);
echo "Ocorrências de 'AAAA': " . implode(", ", $resultado2) . "\n";

// Saída esperada
// Padrão encontrado nos índices: 10
// Ocorrências de 'AAAA': 0, 1

🧠 O Segredo: A Tabela LPS Visualizada

A mágica do KMP está na tabela LPS (Longest Prefix Suffix). Ela responde à pergunta: "Se eu errei aqui, quanto eu posso aproveitar do que já conferi?"

Vamos visualizar para o padrão: ABABAC

O que isso significa na prática? Se estamos comparando e falhamos na letra C (índice 5), a tabela nos diz que o caractere anterior (índice 4) tinha LPS = 3. Isso significa que os 3 primeiros caracteres ("ABA") já foram conferidos e casam! Não precisamos voltar ao início, podemos continuar testando a partir do índice 3 do padrão.

🌊 Exemplo Prático: Scanner de Stream de Logs

O KMP é imbatível quando você não pode voltar atrás. Imagine que você está lendo um log de servidor em tempo real (stream) e quer detectar um padrão de erro crítico ("ERROR:DB_FAIL"). Você recebe caractere por caractere e não pode carregar o arquivo todo na memória.

<?php

class LogStreamScanner {
    private $pattern;
    private $lps;
    private $j = 0; // Estado atual da busca (índice no padrão)

    public function __construct(string $pattern) {
        $this->pattern = $pattern;
        $this->lps = $this->computeLPS($pattern);
    }

    // Pré-processamento (igual ao KMP padrão)
    private function computeLPS($pattern) {
        $m = strlen($pattern);
        $lps = array_fill(0, $m, 0);
        $len = 0;
        $i = 1;
        while ($i < $m) {
            if ($pattern[$i] == $pattern[$len]) {
                $len++;
                $lps[$i] = $len;
                $i++;
            } else {
                if ($len != 0) $len = $lps[$len - 1];
                else { $lps[$i] = 0; $i++; }
            }
        }
        return $lps;
    }

    /**
     * Processa um único caractere do stream.
     * Retorna true se o padrão foi completado neste caractere.
     */
    public function processChar(string $char): bool {
        $m = strlen($this->pattern);

        // Lógica de transição do KMP
        while ($this->j > 0 && $char != $this->pattern[$this->j]) {
            $this->j = $this->lps[$this->j - 1];
        }

        if ($char == $this->pattern[$this->j]) {
            $this->j++;
        }

        if ($this->j == $m) {
            // Padrão encontrado!
            // Reinicia j para LPS do final para permitir overlaps ou continua 0
            // Aqui vamos resetar para buscar a próxima ocorrência
            $this->j = $this->lps[$this->j - 1]; 
            return true;
        }

        return false;
    }
}

// --- Simulação de Stream ---

// Imagine que isso vem de um 'tail -f' ou socket
function geradorDeLog() {
    $logs = "INFO: Start... WARN: Low mem... ERROR:DB_FAIL... INFO: End";
    for ($i = 0; $i < strlen($logs); $i++) {
        yield $logs[$i];
    }
}

$scanner = new LogStreamScanner("ERROR:DB_FAIL");
$encontrou = false;

foreach (geradorDeLog() as $char) {
    if ($scanner->processChar($char)) {
        echo "🚨 ALERTA CRÍTICO ENCONTRADO!\n";
        $encontrou = true;
    }
}

if (!$encontrou) {
    echo "Nenhum erro crítico detectado.\n";
}

// Saída esperada
// 🚨 ALERTA CRÍTICO ENCONTRADO!

Neste exemplo, o LogStreamScanner mantém o estado interno ($j). Ele consome um byte de cada vez e nunca precisa ler o buffer anterior. Isso é impossível com strpos ou força bruta simples sem bufferização complexa.

🎩 Trick: Quando NÃO usar KMP (Otimização Nativa)

Você sabia que na maioria dos casos em PHP, usar strpos() é muito mais rápido que implementar KMP?

Descubra o porquê e veja os benchmarks no nosso trick dedicado:

👉 Por que strpos() é mais rápido que KMP em PHP?

⚠️ Considerações Finais

O KMP é uma ferramenta fundamental no arsenal de algoritmos. Embora raramente implementado do zero em produção web (dada a eficiência das libs nativas em C), ele é a base para processamento de textos em editores, compiladores e sistemas de busca em streams.