De ce contează?
Te uiți la un cuvânt necunoscut și vrei să-i ghicești sensul. Începutul lui — „auto-”, „pre-”, „re-” — îți spune deja multe; și sfârșitul — „-tor”, „-ism”, „-itate” — la fel. Ai folosit fără să știi două idei simple: începutul unui șir (prefixul) și sfârșitul lui (sufixul).
Intuiția
Un prefix este o bucată luată de la începutul șirului, fără goluri: primele câteva caractere, în ordine. Un sufix este o bucată luată de la sfârșitul șirului: ultimele câteva caractere, în ordine.
Pentru șirul "algoritm" (8 caractere, pozițiile 0..7):
- prefixele sunt
"a","al","alg","algo", ... până la tot șirul; - sufixele sunt
"m","tm","itm","ritm", ... până la tot șirul.
Întrebarea practică este aproape mereu: începe șirul cu un anumit tipar? Se termină cu un anumit tipar? De exemplu, "algoritm" începe cu "algo" și se termină cu "ritm".
Vezi cum funcționează
Folosește ← și → ca să pășești caracter cu caracter, sau Redă pentru animație. Vizualizarea alunecă un tipar peste un text și compară literă cu literă. A verifica un prefix sau un sufix e cazul simplu al aceleiași idei: nu mai aluneci tiparul peste tot șirul, ci îl fixezi la un singur loc — la început (pentru prefix) sau la sfârșit (pentru sufix) — și compari caracterele de pe acele poziții.
Ca să verifici dacă "algoritm" începe cu "algo", iei s.substr(0, 4) și compari rezultatul cu "algo". Simplu și citeț.
substr construiește un șir nou de fiecare dată — alocă memorie și copiază caracterele. Pentru o singură verificare e bine, dar dacă verifici mii de prefixe și sufixe (sau o faci într-o buclă), copiezi aceleași caractere iar și iar — risipă de timp și memorie.
Nu ai nevoie de o copie ca să compari. Caracterele tiparului stau deja în șir, pe pozițiile lor. Compari direct s[i] cu tipar[i], fără să muți nimic în altă parte.
Parcurgi tiparul caracter cu caracter pe lungimea lui. Pentru prefix compari s[i] cu p[i] pornind de la poziția 0. Pentru sufix compari aceleași caractere, dar aliniate la coada lui s, pornind de la poziția n - lungimea_tiparului.
Algoritmul pas cu pas
Fie șirul s = "algoritm", cu n = 8 caractere pe pozițiile 0..7.
Începe s cu "algo"? Tiparul are 4 caractere. Comparăm pozițiile 0..3 ale lui s cu pozițiile 0..3 ale tiparului:
a | l | g | o | r | i | t | m |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
p0 | p3 |
a=a, l=l, g=g, o=o — toate patru potrivesc, deci răspunsul este DA.
Se termină s cu "ritm"? Tiparul are tot 4 caractere. Sufixul de lungime 4 începe la poziția n - 4 = 8 - 4 = 4. Comparăm pozițiile 4..7 ale lui s cu pozițiile 0..3 ale tiparului:
a | l | g | o | r | i | t | m |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
start | end |
s[4]=r, s[5]=i, s[6]=t, s[7]=m — se potrivesc cu r-i-t-m, deci răspunsul este DA.
Uneori un prefix este în același timp și sufix al aceluiași șir. Pentru "abcab", prefixul "ab" este identic cu sufixul "ab". Un astfel de prefix-care-e-și-sufix se numește border. Borderele stau la baza algoritmului KMP de căutare rapidă în șiruri: când o potrivire eșuează, KMP folosește cel mai lung border ca să nu o ia de la capăt. Deocamdată e suficient să reții ideea.
Implementare C++
Scriem două funcții care compară caracter cu caracter, fără substr. Returnează true/false.
#include <iostream>
#include <string>
using namespace std;
// incepe s cu tiparul p?
bool incepeCu(const string &s, const string &p) {
if (p.size() > s.size()) return false; // tiparul nu incape
for (int i = 0; i < (int)p.size(); i++) {
if (s[i] != p[i]) return false; // compar prefixul direct
}
return true;
}
// se termina s cu tiparul p?
bool seTerminaCu(const string &s, const string &p) {
if (p.size() > s.size()) return false; // tiparul nu incape
int start = (int)s.size() - (int)p.size(); // pozitia de start a sufixului
for (int i = 0; i < (int)p.size(); i++) {
if (s[start + i] != p[i]) return false; // aliniat la coada lui s
}
return true;
}
int main() {
string s = "algoritm";
cout << incepeCu(s, "algo") << "\n"; // 1 (DA)
cout << seTerminaCu(s, "ritm") << "\n"; // 1 (DA)
cout << incepeCu(s, "alga") << "\n"; // 0 (NU, difera la pozitia 3)
return 0;
}Cheia este start = n - lungime: pentru s = "algoritm" (n=8) și p = "ritm" (lungime 4) obținem start = 4, exact prima poziție a sufixului. De acolo, s[start + i] merge prin s[4], s[5], s[6], s[7], aliniat cap la cap cu p[0], p[1], p[2], p[3].
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Orice caz | O(lungimea tiparului) | O(1) |
Comparăm cel mult atâtea caractere câte are tiparul, și ne oprim mai devreme la prima nepotrivire. Nu copiem nimic — folosim doar câteva variabile, deci spațiul suplimentar este constant.
Trei capcane frecvente:
- Off-by-one la sufix. Poziția de start este
n - lungime, nun - lungime - 1(ai sări un caracter și ai compara greșit) și nun - lungime + 1(ai depăși cu unul și ai pierde primul caracter al sufixului). Pentru"algoritm"și"ritm":8 - 4 = 4, corect. substrinutil. Nu construi o copie doar ca să compari —s.substr(0, 4) == "algo"funcționează, dar alocă memorie de fiecare dată. Compară direct pe poziții.- Tiparul mai lung decât șirul. Dacă verifici prefixul
"algoritmica"(11) într-un șir de 8 caractere și nu testezi întâi lungimea, ajungi să citești în afara șirului. Verifică mereup.size() > s.size()la început și returneazăfalse.