Princípio do Algoritmo KMP

O algoritmo KMP (Knuth-Morris-Pratt) é uma técnica eficiente para encontrar todas as ocorrências de um padrão dentro de um texto. Diferente da abordagem ingênua (força bruta), que tem complexidade O(mn) e realiza comparações redundantes, o KMP utiliza informações sobre o padrão para pular comparações desnecessárias, alcançando complexidade O(n + m).

Por exemplo, ao comparar o texto "ABCDABCDABDE" com o padrão "ABCDABD", após seis correspondências bem-sucedidas, a sétima falha. A força bruta reiniciaria a comparação a partir do segundo caractere do texto, mas o KMP aproveita a estrutura do padrão para otimizar o deslocamento.

Conceito de Border (Borda)

O KMP introduz o conceito de "border", que é o maior prefixo próprio que também é sufixo de uma string. Para a string "abcgab", o border tem compriemnto 2 (correspondendo a "ab"). Esse conceito permite que, em caso de falha na comparação, o padrão seja deslocado de forma que o border já correspondido seja alinhado com o sufixo atual do texto, evitando reinícios do zero.

Construção do Array de Próximos (Next Array)

O array de próximos armazena o comprimento do border mais longo para cada prefixo do padrão. Sua construção é realizada por um processo semelhante a uma auto-correspondência do padrão, onde o padrão é comparado consigo mesmo.

// Construção do array next
int buildNextArray(string pattern) {
    int m = pattern.length();
    int nextArray[m];
    nextArray[0] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = nextArray[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        nextArray[i] = j;
    }
}

Algoritmo de Correspondência KMP

Com o array de próximos construído, a busca do padrão no texto é realizada percorrendo ambos simultaneamente. Quando ocorre uma falha, o padrão é deslocado usando o array de próximos, permitindo que a comparação continue de um ponto avançado.

// Algoritmo KMP para busca
void kmpSearch(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    int nextArray[m];
    buildNextArray(pattern, nextArray);
    
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = nextArray[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
            if (j == m) {
                cout << "Padrão encontrado na posição: " << i - j + 1 << endl;
                j = nextArray[j - 1]; // Permite sobreposições
            }
        }
    }
}

Floresta de Falha (Fail Tree)

O array de próximos pode ser interpretado como uma estrutura de árvore, onde cada nó i tem como pai o valor next[i-1]. Essa floresta de falha é útil em problemas avançados de strings, como manipulação de múltiplos padrões ou operações sobre sobreposições. Exemplos clásicos incluem problemas de template e zoo em competições de programação.