Pe scurt
Un șir de caractere (string) este o structură de date liniară formată dintr-o succesiune de caractere, reprezentată în C prin tablouri de tip char terminate cu NULL. Prelucrările de bază includ citirea, afișarea, calcularea lungimii, copierea, concatenarea, compararea și căutarea, iar la bacalaureat accentul cade pe prelucrări iterative cu indici. Căutarea unui model într-un text se realizează clasic prin metoda „forță brută”, cu complexitate O(n*m).
Reprezentarea și structura șirurilor de caractere
- Șir de caractere (string) – structură de date liniară, formată dintr-o succesiune de caractere
- În C/C++: reprezentat prin tablouri de tip char, terminate cu caracterul NULL ('\0')
- Dimensiunea maximă trebuie cunoscută la declarare
- În Pascal, Python, Java: reprezentat ca obiect specific
- În limbajele high-level (Python, Java): șirurile sunt imutabile, operațiile se fac prin metode specifice (split, join, find, replace)
Prelucrări de bază
- Citirea: fgets, scanf cu %s
- Afișarea
- Calcularea lungimii: strlen
- Copierea: strcpy
- Concatenarea: strcat
- Compararea: strcmp
- Căutarea unui caracter: strchr
- Căutarea unui subșir: strstr
- La bacalaureat: accent pe prelucrări iterative folosind indici, fără a apela funcții de bibliotecă decât în cazuri simple
- Se recomandă utilizarea funcțiilor predefinite din <string.h> sau <cstring> pentru eficiență, dar cunoașterea implementării manuale este binevenită
Căutarea și potrivirea de șabloane
- Căutarea unui model (pattern) într-un text – metoda clasică: forță brută
- Se parcurge textul și, pentru fiecare poziție, se încearcă potrivirea caracter cu caracter a modelului
- Complexitate: **O(n*m) în cel mai rău caz (n = lungimea textului, m = lungimea modelului)
- Potrivirea de șabloane (pattern matching) mai eficientă – algoritmi avansați (KMP, Rabin-Karp, Boyer-Moore), dar la liceu se studiază doar varianta naivă
- Esențial: manipularea corectă a indecșilor, evitarea depășirii capetelor șirurilor și terminarea corectă cu NULL în C
Probleme frecvente la bacalaureat
- Numărarea aparițiilor unui caracter sau cuvânt
- Extragerea cuvintelor dintr-un text
- Înlocuirea unor secvențe
- Verificarea palindroamelor
- Criptarea simplă (Cezar, substituție)
- Citirea unui text linie cu linie
- Prelucrarea propozițiilor
- Determinarea frecvenței literelor
- Eliminarea spațiilor multiple
- Conversia la litere mari/mici
Concepte avansate
- Complexitatea algoritmilor
- Vectori de frecvență pentru caractere (de exemplu, pentru a verifica anagramele)
- Sortarea șirurilor cu ajutorul funcției qsort
Exemple practice
Exemplul 1: Calcularea lungimii unui șir fără strlen
- În C, se parcurge șirul cu un contor până la '\0'
- Cod: int lungime = 0; while (s[lungime] != '\0') lungime++; printf("Lungimea este %d", lungime);
- Explicație: se incrementează contorul cât timp nu s-a atins terminatorul
Exemplul 2: Căutarea naivă a unui subșir 'abcd' în textul 'xabcde'
- Se parcurge textul de la i=0 la n-m; pentru fiecare i, se compară caracterele modelului cu cele ale textului
- Dacă toate coincid, se afișează poziția
- Implementare în C: for(i=0; i<=n-m; i++) { j=0; while(j<m && text[i+j]==model[j]) j++; if(j==m) printf("Găsit la %d", i); }
Exemplul 3: Eliminarea tuturor spațiilor multiple dintr-un șir
- Se construiește un nou șir, copiind caracterele, dar adăugând un singur spațiu atunci când se întâlnesc mai multe spații consecutive
- Se păstrează un flag ultimulSpatiu**
- Dacă caracterul curent este spațiu și flagul este true, se sare; altfel, se adaugă caracterul și se actualizează flagul
Verifică-te!
- Cum se reprezintă un șir de caractere în limbajul C și care este rolul caracterului NULL?
- Care este complexitatea algoritmului naiv de căutare a unui subșir și de ce depinde aceasta?
- Ce metodă se folosește pentru a elimina spațiile multiple dintr-un șir și ce rol joacă flagul „ultimulSpatiu”?