Prefixe și sufixe — începuturi și finaluri

De ce contează?

Un nume de fișier ca poza.jpg îți spune două lucruri prin capete: începutul (poza) zice cum se numește, iar finalul (.jpg) zice ce tip e. Verificările „începe cu” și „se termină cu” sunt despre prefixe și sufixe.

Ce sunt prefixele și sufixele?

Un prefix este o bucată de la începutul șirului. Un sufix este o bucată de la finalul lui. Pentru s = "tren":

Prefixe: t, tr, tre, tren
Sufixe: n, en, ren, tren

s	t	r	e	n
index	0	1	2	3

Prefixul de lungime 3 = primele 3 caractere („tre”), de la indexul 0.

s	t	r	e	n
index	0	1	2	3

Sufixul de lungime 3 = ultimele 3 caractere („ren”), de la indexul 1.

Cum le extragi

Cu substr, totul se reduce la indecși:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s = "tren";
    int k = 3;
    cout << s.substr(0, k) << "\n";            // tre  (prefix de lungime k)
    cout << s.substr(s.size() - k) << "\n";    // ren  (sufix de lungime k)
    return 0;
}

Observația-cheie

Prefixul de lungime k începe la indexul 0. Sufixul de lungime k începe la indexul n - k. Tot ce trebuie e să nu greșești punctul de start.

„Începe cu” și „se termină cu”

O sarcină foarte des întâlnită: verifici dacă un șir începe sau se termină cu un anumit tipar p.

#include <iostream>
#include <string>
using namespace std;

bool incepeCu(string s, string p) {
    if (p.size() > s.size()) return false;        // p mai lung -> imposibil
    return s.substr(0, p.size()) == p;            // primele |p| caractere
}

bool seterminaCu(string s, string p) {
    if (p.size() > s.size()) return false;
    return s.substr(s.size() - p.size()) == p;    // ultimele |p| caractere
}

int main() {
    cout << incepeCu("poza.jpg", "poza") << "\n";       // 1
    cout << seterminaCu("poza.jpg", ".jpg") << "\n";    // 1
    cout << seterminaCu("poza.jpg", ".png") << "\n";    // 0
    return 0;
}

De ce verificăm întâi lungimea? Dacă p e mai lung decât s, scăderea s.size() - p.size() (pe tipuri fără semn) devine un număr uriaș și substr aruncă excepție. Testul de lungime te apără.

Comparație fără substr (mai eficient)

substr creează un șir nou (costă memorie). Pentru viteză, compari caracter cu caracter, fără copie:

bool incepeCuRapid(string s, string p) {
    if (p.size() > s.size()) return false;
    for (int i = 0; i < (int)p.size(); i++)
        if (s[i] != p[i]) return false;   // diferenta -> nu e prefix
    return true;
}

Complexitate

Operație	Timp	Spațiu
`substr` prefix/sufix	O(k)	O(k) (copie)
„începe cu” / „se termină cu” cu comparație directă	O(\|p\|)	O(1)

Greșeli frecvente

Greșeli frecvente de concurs:

Sufix greșit: s.substr(k) dă sufixul care începe la indexul k, NU sufixul de lungime k. Pentru lungime k folosește s.substr(s.size() - k).
Scădere fără semn: s.size() - p.size() când p e mai lung devine uriaș; testează lungimile întâi.
find în loc de prefix: s.find(p) == 0 merge pentru prefix, dar find parcurge tot șirul degeaba; comparația directă e mai clară și mai rapidă.
substr în buclă: construiește copii repetate — O(n²) ascuns. Compară direct.

Recapitulare

Prefixul de lungime k începe la 0; sufixul de lungime k începe la n - k.
s.substr(0, k) și s.substr(n - k) extrag prefixul/sufixul.
Pentru „începe/se termină cu”, verifică întâi lungimea, apoi compară — direct, fără copie, e O(|p|) și O(1) memorie.