Programare Competitivă

Algoritmul KMP (Knuth-Morris-Pratt)

KMP este un algoritm pentru căutarea unui șablon p într-un text s, garantat O(n + m) în cazul cel mai rău.

Spre deosebire de Rabin-Karp (care e O(n+m) doar în medie), KMP e determinist - nu depinde de coliziuni de hash.

Problema

Text s de lungime n, șablon p de lungime m. Găsim toate pozițiile unde apare p în s.

s = "abababcab"
p = "ababc"

Apariția: poziția 2 (s[2..6] = "ababc")

De ce nu merge cel naiv?

Soluția naivă O(n*m) compară caracter cu caracter și, la eșec, se întoarce la poziția i+1 din s și reîncepe de la p[0]. Refacem munca deja făcută.

s = "ababababc"
p = "ababc"

Încercare 1: s[0..4] = "ababa" ≠ "ababc" - eșec la poziția 4
Încercare 2: pornim de la s[1] - "babab..." - eșec imediat
...

KMP evită asta prin prefix function.

Prefix function (π)

Pentru un șir p, π[i] = cea mai lungă lungime k < i+1 astfel încât prefixul p[0..k-1] este egal cu sufixul p[i-k+1..i].

Cu alte cuvinte: cel mai lung prefix propriu care e și sufix pentru p[0..i].

Exemplu

p = "a b c a b c d"
     0 1 2 3 4 5 6

π[0]: "a" - prefix propriu nul → π[0] = 0
π[1]: "ab" - prefixele propii: "a". Sufixele (fără el însuși): "b". Nu coincid → π[1] = 0
π[2]: "abc" - "a", "ab" vs "c", "bc" → π[2] = 0
π[3]: "abca" - "a" = "a" → π[3] = 1
π[4]: "abcab" - "ab" = "ab" → π[4] = 2
π[5]: "abcabc" - "abc" = "abc" → π[5] = 3
π[6]: "abcabcd" - niciun prefix = sufix → π[6] = 0

π = [0, 0, 0, 1, 2, 3, 0]

Calculul prefix function - O(m)

int pi[1001];

void prefixFunction(const char *p, int m)
{
    pi[0] = 0;
    int k = 0;
    for (int i = 1; i < m; i++) {
        // Daca nu se potriveste, sarim inapoi folosind pi
        while (k > 0 && p[k] != p[i])
            k = pi[k - 1];

        if (p[k] == p[i])
            k++;

        pi[i] = k;
    }
}

De ce e O(m)?

k crește cu cel mult 1 la fiecare iterație (total m). Descreșterile sunt mărginite de creșteri (nu poate scădea mai mult decât a crescut). Deci amortizat O(m).

Căutarea KMP

Folosim π ca să “sărim” inteligent în șablon când potrivirea eșuează.

void kmp(const char *s, int n, const char *p, int m)
{
    prefixFunction(p, m);

    int k = 0; // cate caractere din p am potrivit pana acum
    for (int i = 0; i < n; i++) {
        // Daca nu se potriveste, sarim folosind pi
        while (k > 0 && p[k] != s[i])
            k = pi[k - 1];

        if (p[k] == s[i])
            k++;

        // Am gasit o potrivire completa
        if (k == m) {
            fout << (i - m + 1) << " ";
            k = pi[k - 1]; // continuam cautarea
        }
    }
}

Complexitate: O(n + m) garantat.

Cod complet

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

char s[1000001];
char p[1001];
int pi[1001];

void prefixFunction(const char *p, int m)
{
    pi[0] = 0;
    int k = 0;
    for (int i = 1; i < m; i++) {
        while (k > 0 && p[k] != p[i])
            k = pi[k - 1];
        if (p[k] == p[i])
            k++;
        pi[i] = k;
    }
}

int main()
{
    fin >> s >> p;

    int n = strlen(s);
    int m = strlen(p);

    prefixFunction(p, m);

    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k > 0 && p[k] != s[i])
            k = pi[k - 1];

        if (p[k] == s[i])
            k++;

        if (k == m) {
            fout << (i - m + 1) << " ";
            k = pi[k - 1];
        }
    }

    return 0;
}

date.in:

abababcab
ababc

date.out:

2

Pas cu pas: căutăm "ababc" în "abababcab"

Prefix function pentru p = "ababc"

π = [0, 0, 1, 2, 0]
  • π[0] = 0
  • π[1] = 0 (“a” ≠ “b”)
  • π[2] = 1 (“a” = “a”)
  • π[3] = 2 (“ab” = “ab”)
  • π[4] = 0 (niciun prefix = sufix)

Parcurgerea lui s = "abababcab"

i s[i] k înainte Acțiune k după
0 a 0 p[0]=‘a’ = s[0]=‘a’ → k++ 1
1 b 1 p[1]=‘b’ = s[1]=‘b’ → k++ 2
2 a 2 p[2]=‘a’ = s[2]=‘a’ → k++ 3
3 b 3 p[3]=‘b’ = s[3]=‘b’ → k++ 4
4 a 4 p[4]=‘c’ ≠ ‘a’ → k = π[3] = 2. p[2]=‘a’ = ‘a’ → k++ 3
5 b 3 p[3]=‘b’ = ‘b’ → k++ 4
6 c 4 p[4]=‘c’ = ‘c’ → k++. k=5=m → Match la i-m+1 = 2. k = π[4] = 0 0
7 a 0 p[0]=‘a’ = ‘a’ → k++ 1
8 b 1 p[1]=‘b’ = ‘b’ → k++ 2

Match găsit la poziția 2.

Observă magia la i=4: în loc să ne întoarcem la i=1 și să reîncepem de la p[0], folosim π[3]=2 - am “memorat” că ultimele 2 caractere potrivite (“ab”) sunt și prefix al lui p, deci pornim de acolo.

Intuiția prefix function

Gândește-te că ai potrivit p[0..k-1] și acum p[k] ≠ s[i]. Ce poți reutiliza?

Cel mai lung sufix al lui p[0..k-1] care e și prefix al lui p. Dacă acel prefix are lungime π[k-1], atunci știi deja că p[0..π[k-1]-1] se potrivește cu ultimele caractere din s. Continui de acolo.

Comparație cu Rabin-Karp: ambele sunt O(n+m), dar KMP e garantat (nu depinde de coliziuni). Rabin-Karp e mai flexibil pentru căutări multiple și hash pe subșiruri.

Aplicații ale prefix function

1. Numărul de apariții ale fiecărui prefix într-un șir

Pentru fiecare prefix p[0..i], câte poziții îl conțin ca sufix în întreg șirul.

2. Compresia unui șir (cea mai mică perioadă)

Un șir p de lungime m are perioada m - π[m-1] dacă (m - π[m-1]) divide m.

p = "ababab"
π = [0, 0, 1, 2, 3, 4]
Perioada = 6 - 4 = 2 → "ab" se repetă de 3 ori

3. Numărul de subșiruri distincte

Folosind prefix function pe șiruri adăugând caractere, se poate număra în O(n²).

4. Construirea unui automat finit

KMP poate fi văzut ca un automat care, la fiecare caracter citit, știe deterministic în ce stare trece.

Complexitate

Timp Memorie
Naive O(n * m) O(1)
Rabin-Karp O(n + m) mediu O(1)
KMP O(n + m) garantat O(m)
Z-algoritm O(n + m) garantat O(n + m)
Suffix Automaton O(n + m) O(n)

KMP vs Rabin-Karp

KMP Rabin-Karp
Idee Prefix function Hash polinomial
Garantat O(n+m) Da Nu (coliziuni)
Șabloane multiple Greu Ușor (set de hash-uri)
Implementare Mai complexă Mai simplă
Memorie O(m) O(1)

KMP e alegerea default dacă ai nevoie de garanție. Rabin-Karp e mai bun când cauți multiple șabloane simultan.

Greșeli frecvente

1. Confuzia între k și i

// k = cate caractere din p am potrivit (0..m)
// i = pozitia curenta in s (0..n-1)

k e un indice în p, i e un indice în s. Nu le amesteca.

2. pi[k - 1] vs pi[k]

// CORECT - sarim folosind prefix function pentru ultimul caracter potrivit
k = pi[k - 1];

// GRESIT - depaseste potentia limita
k = pi[k];

3. Uitarea resetării după match

if (k == m) {
    fout << (i - m + 1) << " ";
    k = pi[k - 1]; // NU uita! continuam cautarea
}

Dacă pui k = 0, pierzi potențiale overlap-uri (ex: p = "aa" în s = "aaaa" are 3 apariții: 0, 1, 2).

4. Testul while k > 0

while (k > 0 && p[k] != s[i])  // important: k > 0
    k = pi[k - 1];

Dacă uiți k > 0, vei accesa pi[-1] și programul va crăpa.

Exemplu: numărul de apariții

Câte ori apare "aba" în "ababababa"?

s = "ababababa"
p = "aba"
π = [0, 0, 1]

i=0: k=1 (potrivim 'a')
i=1: k=2 (potrivim 'b')
i=2: k=3=m → match la 0. k = π[2] = 1
i=3: p[1]='b' = s[3]='b' → k=2
i=4: p[2]='a' = s[4]='a' → k=3 → match la 2. k = π[2] = 1
i=5: p[1]='b' = s[5]='b' → k=2
i=6: p[2]='a' = s[6]='a' → k=3 → match la 4. k = π[2] = 1
i=7: p[1]='b' = s[7]='b' → k=2
i=8: p[2]='a' = s[8]='a' → k=3 → match la 6. k = π[2] = 1

4 apariții (pozițiile 0, 2, 4, 6), cu overlap.

Ce să reții

  • KMP caută un șablon într-un text în O(n + m) garantat.
  • Prefix function π[i] = cel mai lung prefix propriu care e și sufix pentru p[0..i].
  • Calculul π se face în O(m) amortizat.
  • La nepotrivire, în loc să ne întoarcem, folosim π pentru a sări “inteligent”.
  • KMP e alternativa deterministă la Rabin-Karp.
  • Prefix function are aplicații multiple: perioada unui șir, numărul de apariții ale prefixelor, compresii.
Cuprins Inapoi Inainte