De ce contează?
Te uiți la cuvântul „abcab" și observi ceva: începe cu „ab" și se termină tot cu „ab". Aceeași bucată apare și la cap, și la coadă. Dacă ai un șir lung și vrei să știi cât din început se repetă fix la sfârșit, ai nevoie de o noțiune precisă — prefixul care e și sufix. Pe ea se sprijină căutarea rapidă de subșiruri și detectarea periodicității.
Intuiția
Un prefix este orice început al șirului: pentru „abcab", prefixele sunt „a", „ab", „abc", „abca", „abcab". Un sufix este orice sfârșit: „b", „ab", „cab", „bcab", „abcab". Întrebarea-cheie de concurs: care e cel mai lung prefix care e în același timp și sufix, fără să fie tot șirul? Îl numim border. Pentru „abcab" răspunsul este „ab", lungime 2.
Vorbim mereu de border propriu: nu se pune la socoteală tot șirul (care e trivial și prefix, și sufix al lui însuși). Și nici prefixul vid nu ne ajută la nimic — căutăm cea mai lungă potrivire utilă.
Vezi cum funcționează
Pornește animația și urmărește cum, la o nepotrivire, căutarea nu o ia de la capăt în șir, ci „sare" înapoi exact cât îi spune borderul deja calculat. Acolo se vede de ce prefixele-sufixe fac căutarea rapidă.
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Observă că la o nepotrivire indicele din text nu se întoarce — doar indicele din tipar coboară pe un border mai scurt.
Vrei borderul cel mai lung pentru fiecare prefix. Prima idee: pentru fiecare
lungime L de la cea mai mare în jos, compari litera cu literă începutul de
lungime L cu sfârșitul de lungime L. Primul care se potrivește e răspunsul.
Ai până la n lungimi de testat, iar o singură comparație prefix-sufix poate
parcurge până la n caractere. Pentru un șir de lungime 100000 ajungi la
ordinul a 10 miliarde de operații — O(n^2), mult peste limita de timp.
Nu recalcula de la zero. Borderul de pe poziția i se obține din borderul de
pe poziția i-1: încerci să-l prelungești cu o literă. Dacă litera nu se
potrivește, „cazi" pe un border mai scurt (borderul borderului) și încerci din
nou — nu reiei niciodată din șir.
Construiești tabelul pi, unde pi[i] = lungimea celui mai lung border al
prefixului care se termină la poziția i. O singură parcurgere, fiecare literă
e vizitată o dată: O(n). Acesta e exact tabelul folosit de KMP.
Algoritmul pas cu pas
Construim pi pentru șirul „abcab" (indexat de la 0). pi[i] este lungimea
celui mai lung prefix care e și sufix al porțiunii de la 0 la i.
pi[0] este mereu 0: un singur caracter nu are border propriu.
a | b | c | a | b |
0 | 1 | 2 | 3 | 4 |
pi=0 |
La pozițiile 1 și 2 nicio literă nu reia începutul: „ab" nu are „a" la coadă, iar „abc" nu se termină cu „a". Ambele rămân 0.
a | b | c | a | b |
0 | 1 | 2 | 3 | 4 |
pi=0 |
La poziția 3 ajungem la al doilea „a". El coincide cu prima literă „a", deci borderul are lungime 1:
a | b | c | a | b |
0 | 1 | 2 | 3 | 4 |
pi=1 |
La poziția 4 litera „b" prelungește borderul: după „a" urmează „b", la fel ca la început. Borderul devine „ab", lungime 2:
a | b | c | a | b |
0 | 1 | 2 | 3 | 4 |
pi=2 |
Tabelul complet pi pentru „abcab" este astfel [0, 0, 0, 1, 2]:
0 | 0 | 0 | 1 | 2 |
0 | 1 | 2 | 3 | 4 |
Cheia construcției: când litera nouă nu prelungește borderul curent de
lungime k, nu o iei de la 0 — sari la pi[k-1], adică la borderul borderului,
și reîncerci. Fiecare literă urcă borderul cel mult o dată, deci totalul rămâne
liniar.
Implementare C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Construieste tabelul functiei de prefix pentru sirul s.
// pi[i] = lungimea celui mai lung prefix al lui s care e si sufix al lui s[0..i].
vector<int> functiaDePrefix(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int k = pi[i - 1]; // lungimea borderului de pe pozitia anterioara
// cat timp litera nu prelungeste borderul, cazi pe un border mai scurt
while (k > 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k++; // litera prelungeste borderul
}
pi[i] = k;
}
return pi;
}
int main() {
string s = "abcab";
vector<int> pi = functiaDePrefix(s);
for (int x : pi) {
cout << x << " ";
}
// Afiseaza: 0 0 0 1 2
return 0;
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Naiv (testezi fiecare lungime) | O(n²) | O(1) |
Funcția de prefix (pi) | O(n) | O(n) |
Deși bucla while pare că poate rula de multe ori, valoarea lui k urcă cu cel
mult 1 la fiecare pas și nu poate coborî mai mult decât a urcat în total — deci
toate coborârile însumate sunt O(n).
Două capcane clasice:
Prima — confuzia prefix propriu vs. impropriu. Borderul nu are voie să fie
tot șirul. Pentru „aaaa", borderul lui „aaaa" este „aaa" (lungime 3), nu „aaaa".
Dacă uiți condiția, pi[i] ajunge egal cu i+1 și KMP intră în buclă infinită.
A doua — resetarea greșită la nepotrivire. Tentația e să pui k = 0 când
litera nu se potrivește. Greșit: trebuie k = pi[k-1], ca să nu pierzi
border-urile mai scurte care încă pot fi valide. Resetul brutal la 0 dă
rezultate greșite pe șiruri cu repetiții, de exemplu „aabaaab".