Nota: todos os índices utilizados neste artigo são baseados em zero.

Prefixos e sufixos

Dado uma string s, um prefixo é qualquer substring que inicia na primeira posição de s. O prefixo que termina na posição i é denotado por s[0..i]. Um prefixo próprio é todo prefixo de s diferente dela mesma.

De forma análoga, um sufixo é uma substring que termina na última posição de s. Um sufixo próprio é qualquer sufixo de s exceto a própria string.

Por exemplo, para s = "abcabeda", seus prefixos próprios são "a", "ab", "abc", "abca", "abcabe", "abcabed", enquanto seus sufixos próprios incluem "a", "da", "eda", "beda", "abeda", "cabeda", "bcabeda".

Função de prefixo (função pi)

A função de prefixo de uma string s, geralmente denotada por pi, associa a cada posição i o comprimento do maior prefixo próprio de s[0..i] que também é sufixo dessa substring.

Formalmente:

pi[i] = max { k | 0 ≤ k ≤ i e s[0..k-1] = s[i-k+1..i] }

Por definição, pi[0] = 0, pois uma substring de um único caractere não possui prefixo próprio.

Exemplo

Para s = "abacaba":

• pi[0] = 0 — apenas "a";
• pi[1] = 0 — "ab" não tem prefixo e sufixo comuns;
• pi[2] = 1 — em "aba", "a" é prefixo e sufixo próprio;
• pi[3] = 0 — "abac" não possui coincidência;
• pi[4] = 1 — em "abaca", apenas "a" coincide;
• pi[5] = 2 — em "abacab", "ab" é prefixo e sufixo;
• pi[6] = 3 — em "abacaba", "aba" é o maior prefixo/sufixo comum.

Construção eficiente da função de prefixo

Uma observação importante é que, ao avançarmos para a próxima posição, o valor de pi[i] pode aumentar no máximo uma unidade. Se o próximo caractere continua o prefixo já encontrado, incrementamos o valor; caso contrário, recuamos para o maior prefixo próprio anterior e tentamos novamente.

Essa ideia permite calcular toda a função em tempo linear.

void prefix_function(const string &s) {
    int n = s.size();
    pi[0] = 0;
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            ++j;
        }
        pi[i] = j;
    }
}

Algoritmo de Knuth-Morris-Pratt

O KMP resolve o problema de encontrar todas as ocorrências de um padrão p dentro de um texto t. A ideia central é calcular a função de prefixo para a string concatenada p + '#' + t, onde '#' é um caractere separador que não aparece em p nem em t.

Ao processarmos essa concatenação, quando pi[i] for igual ao comprimento de p, isso significa que o padrão ocorre no texto terminando na posição correspondente a i. Convertendo o índice para o texto original, a posição inicial (0-indexada) da ocorrência é i - 2 * |p|.

Implementação completa

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
int pi[MAXN];

void prefix_function(const string &s) {
    int n = s.size();
    pi[0] = 0;
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            ++j;
        }
        pi[i] = j;
    }
}

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

    string padrao, texto;
    cin >> padrao >> texto;

    string concat = padrao + "#" + texto;
    prefix_function(concat);

    int p = padrao.size();
    for (int i = p + 1; i < (int)concat.size(); ++i) {
        if (pi[i] == p) {
            cout << (i - 2 * p) << '\n';
        }
    }

    return 0;
}

Assintoticamente, o algoritmo consome tempo O(|p| + |t|) e memória O(|p| + |t|) para armazenar a concatenação e os valores de pi.