KMP (Knuth-Morris-Pratt)

O KMP otimiza a correspondência de padrões ao reutilizar informações de correspondências anteriores. Em vez de reiniciar a busca do início após uma falha, ele utiliza um pré-processamento para determinar o próximo ponto de comparação, reduzindo a complexidade para O(n + m).

O pré-processamento calcula o array de falha, denominado falha[i], que armazena o comprimanto do maior prefixo que também é sufixo para o substring padrão[1..i]. Esse array atua como uma máquina de estados para guiar a correspondência.

A implementação a seguir demonstra o algoritmo KMP:

const int MAX_TAM = 1000000; char texto[MAX_TAM], padrao[MAX_TAM]; int falha[MAX_TAM];

void preProcessar(int comprimentoPadrao) { int ponteiro = 0; for (int i = 2; i <= comprimentoPadrao; ++i) { while (ponteiro > 0 && padrao[i] != padrao[ponteiro + 1]) ponteiro = falha[ponteiro]; if (padrao[i] == padrao[ponteiro + 1]) ++ponteiro; falha[i] = ponteiro; } }

void buscarKMP(int comprimentoTexto, int comprimentoPadrao) { int ponteiro = 0; for (int i = 1; i <= comprimentoTexto; ++i) { while (ponteiro > 0 && texto[i] != padrao[ponteiro + 1]) ponteiro = falha[ponteiro]; if (texto[i] == padrao[ponteiro + 1]) ++ponteiro; if (ponteiro == comprimentoPadrao) { cout << i - comprimentoPadrao + 1 << '\n'; ponteiro = falha[ponteiro]; } } }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

cin >> (texto + 1) >> (padrao + 1);
int lenTexto = strlen(texto + 1);
int lenPadrao = strlen(padrao + 1);

preProcessar(lenPadrao);
buscarKMP(lenTexto, lenPadrao);

for (int i = 1; i <= lenPadrao; ++i) 
    cout << falha[i] << " ";
    
return 0;

}

</details>### Conceito de Bordas (Borders)

O array de falha baseia-se no cnoceito de bordas, que são prefixos que também são sufixos de uma string. Considere uma falha durante a correspondência: quando os caracteres `texto[i]` e `padrão[j]` não correspondem, o KMP busca o maior `k` tal que `padrão[1..k]` seja sufixo de `padrão[1..j]`, permitindo que `j` seja reajustado para `k`.

Essa abordagem garante que todas as bordas sejam exploradas eficientemente, mantendo a complexidade linear, pois o ponteiro do padrão avança e retrocede no máximo O(n) vezes.

### Problema P3426

Um problema relacionado pode ser resolvido usando DP com o array de falha. Defina `dp[i]` como a resposta mínima para os primeiros `i` caracteres. A transição ocorre via bordas: `dp[i] = dp[falha[i]]` se a borda cobrir uma posição válida; caso contrário, `dp[i] = i`.

Implementação simplificada:

<details><summary>Exibir código</summary>```
#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 500000;
char str[MAX_N];
int falha[MAX_N], dp[MAX_N], alcance[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> (str + 1);
    int n = strlen(str + 1);
    
    int ponteiro = 0;
    for (int i = 2; i <= n; ++i) {
        while (ponteiro > 0 && str[i] != str[ponteiro + 1]) 
            ponteiro = falha[ponteiro];
        if (str[i] == str[ponteiro + 1]) 
            ++ponteiro;
        falha[i] = ponteiro;
    }
    
    dp[1] = alcance[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (alcance[dp[falha[i]]] + dp[falha[i]] >= i) {
            dp[i] = dp[falha[i]];
            alcance[dp[falha[i]]] = i;
        } else {
            dp[i] = alcance[i] = i;
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}

O SAM é uma estrutura de dados que rerpesenta todos os sufixos de uma string em um grafo direcionado, construído em tempo linear. Ele permite operações como correspondência de sufixos e busca de substrings com eficiência.

Posições Finais (endpos)

Para qualquer substring t da string s, endpos(t) é o conjunto de posições onde t termina. Substrings com o mesmo conjunto endpos formam uma classe de equivalência, e cada estado do SAM corresponde a uma dessas classes.

Propriedades incluem: se u é sufixo de w, então endpos(u) contém endpos(w). Além disso, os comprimentos das substrings em uma classe formam um intervalo contínuo.

Link de Sufixo (link)

O link de sufixo conecta um estado a outro que representa a maior borda da substring correspondente, semelhante aos links de falha em autômatos de Aho-Corasick. Esse mecanismo permite navegar eficientemente pelas classes de equivalência.