O algoritmo Knuth-Morris-Pratt, ou KMP, é um dos métodos mais eficientes para busca de padrões em strings. Diferente da abordagem de força bruta (Brute Force), que reinicia a comparação do zero a cada falha, o KMP utiliza o conhecimento adquirido em comparações parciais anteriores para evitar verificações redundantes.

O Conceito de Prefixos e Sufixos

A base do KMP reside na análise do próprio padrão (a string que desejamos encontrar) antes de iniciar a busca no texto principal. Para isso, precisamos entender dois conceitos fundamentais:

• Prefixo Próprio: Qualquer substring que comece no início da string, mas não inclua a string inteira.
• Sufixo Próprio: Qualuqer substring que termine no final da string, mas não inclua a string inteira.

O objetivo é encontrar o comprimento do maior prefixo que também é um sufixo para cada subpadrão. Observe os exemplos abaixo:

A Lógica de Funcionamento do KMP

Quando ocorre uma falha de correspondência (mismatch) entre o padrão e o texto, o algoritmo de força bruta desloca o padrão apenas uma posição à frente. O KMP, por outro lado, consulta uma tabela pré-computada (chamada de next ou LPS - Longest Prefix Suffix) para determinar para onde o ponteiro do padrão deve "saltar".

O princípio é simples: se já sabemos que uma parte do padrão coincidiu com o texto, e essa parte possui um prefixo que é igual ao seu sufixo, podemos alinhar esse prefixo diretamente sobre o sufixo correspondente no texto, economizando comparações.

Regras principais:

1. O deslocamento do padrão depende exclusivamente da estrutura do próprio padrão, não do texto principal.
2. Ao falhar no caractere na posição j, o próximo caractere a ser comparado no padrão será o indicado por next[j].

Implementação da Tabela de Saltos (Next)

A tabela next armazena o índice para o qual o ponteiro do padrão deve retornar após uma falha. Se o primeiro caractere falhar, o valor é geralmente definido como -1, sinalizando que o ponteiro do texto deve avançar.

void construir_tabela_saltos(const char *padrao, int *tabela) {
    int m = strlen(padrao);
    int i = 0;
    int j = -1;
    tabela[0] = -1;

    while (i < m - 1) {
        if (j == -1 || padrao[i] == padrao[j]) {
            i++;
            j++;
            tabela[i] = j;
        } else {
            j = tabela[j];
        }
    }
}

Busca com o Algoritmo KMP

Com a tabela pronta, a busca percorre o texto de forma linear. Quando os caracteres coincidem, ambos os ponteiros avançam. Quando divergem, apenas o ponteiro do padrão retrocede conforme a tabela next.

int executar_busca_kmp(const char *texto, const char *padrao) {
    int n = strlen(texto);
    int m = strlen(padrao);
    int *tabela_next = (int *)malloc(sizeof(int) * m);
    
    construir_tabela_saltos(padrao, tabela_next);

    int idx_t = 0; // Índice para o texto
    int idx_p = 0; // Índice para o padrão

    while (idx_t < n && idx_p < m) {
        if (idx_p == -1 || texto[idx_t] == padrao[idx_p]) {
            idx_t++;
            idx_p++;
        } else {
            idx_p = tabela_next[idx_p];
        }
    }

    free(tabela_next);

    if (idx_p == m) {
        return idx_t - m; // Retorna a posição inicial da ocorrência
    }
    return -1; // Padrão não encontrado
}

Otimização da Tabela Next

Existe um caso específico onde a tabela next padrão pode ser ineficiente: quando o caractere de falha no padrão é igual ao caractere para o qual o ponteiro é redirecionado. Nesses casos, sabemos de antemão que a próxima comparação também falhará.

Para corrigir isso, podemos aplicar uma pequena lógica adicional durante a construção da tabela (frequentemente chamada de NextVal):

void construir_tabela_otimizada(const char *p, int *next_val) {
    int m = strlen(p);
    int i = 0;
    int j = -1;
    next_val[0] = -1;

    while (i < m - 1) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            // Se o caractere seguinte for igual, salte para o next do anterior
            if (p[i] != p[j]) {
                next_val[i] = j;
            } else {
                next_val[i] = next_val[j];
            }
        } else {
            j = next_val[j];
        }
    }
}

Essa otimização reduz o número de saltos itnernos no padrão quando caracteres repetidos estão presentes, tornando o tempo de execução no pior caso ainda mais estável.