Prefixe și sufixe

De ce contează?

Când scrii într-o bară de căutare „bucu", aplicația îți propune „București", „Bucureșteni"... Toate au în comun începutul „bucu" — adică un prefix. Iar terminațiile gramaticale („...escu", „...eanu") sunt sufixe. A lucra cu începuturi și terminații de cuvinte e o operație de zi cu zi.

Ce sunt prefixele și sufixele

Un prefix este o secvență care începe de la primul caracter al șirului.
Un sufix este o secvență care se termină cu ultimul caracter al șirului.

Pentru "concurs", "con" e prefix, "urs" e sufix. Întregul șir și șirul vid sunt, formal, și prefixe și sufixe.

Observația-cheie

Un șir de lungime n are exact n + 1 prefixe (de lungime 0, 1, ..., n) și tot atâtea sufixe. Definiția contează: un prefix nu „plutește" la mijloc — e legat de început.

Prefixul de lungime 3 al lui "concurs":

s	c	o	n	c	u	r	s
index	0	1	2	3	4	5	6

Prefixul de lungime 3 este s.substr(0, 3) = „con” — pornește de la index 0.

Iar sufixul de lungime 3:

s	c	o	n	c	u	r	s
index	0	1	2	3	4	5	6

Sufixul de lungime 3 este s.substr(s.size() - 3) = „urs” — se termină la index 6.

Cum le extragi

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

int main() {
    string s = "concurs";
    int n = s.size();

    cout << s.substr(0, 3) << endl;        // con (prefix de lungime 3)
    cout << s.substr(n - 3) << endl;       // urs (sufix de lungime 3)
    cout << s.substr(n - 3, 3) << endl;    // urs (echivalent)
    return 0;
}

„Începe cu" / „Se termină cu"

O verificare foarte des cerută la concursuri:

bool incepeCu(const string& s, const string& t) {
    if (t.size() > s.size()) return false;
    return s.substr(0, t.size()) == t;
}

bool seTerminaCu(const string& s, const string& t) {
    if (t.size() > s.size()) return false;
    return s.substr(s.size() - t.size()) == t;
}

Complexitate

Operație	Timp	Spațiu
Extragere prefix/sufix de lungime k	O(k)	O(k)
„începe cu" / „se termină cu" t	O(\|t\|)	O(\|t\|)

Greșeli frecvente

Capcane reale:

Sufix greșit calculat. s.substr(s.size() - k) cere k <= s.size(); altfel size() - k (unsigned) devine uriaș → excepție. Verifică lungimea înainte.
Confunzi sufixul cu un subșir oarecare. „urs" e sufix doar pentru că se termină exact la finalul șirului; un subșir de la mijloc nu e nici prefix, nici sufix.
Compari lungimi cu semn diferit. t.size() > s.size() e ok, dar s.size() - t.size() fără verificarea de mai sus se sucește pe unsigned.
Uiți cazul t mai lung decât s. Fără if-ul de la început, „începe cu" pică pe substr.

Recapitulare

Prefixul pornește de la primul caracter, sufixul se termină la ultimul.
Prefix de lungime k: s.substr(0, k); sufix de lungime k: s.substr(s.size() - k).
Verifică mereu k <= s.size() — size() e unsigned și scăderea se poate suci.