Siruri de caractere (prelucrari, functii predefinite, palindrom, anagrame)

Pe scurt

Un șir de caractere (string) este o secvență ordonată de caractere, implementată în C++ prin tablouri de tip char sau clasa std::string. Pentru Bacalaureat, trebuie cunoscute funcțiile predefinite din <cstring> (precum strlen, strcpy, strcat, strcmp) și metodele clasei std::string (.length(), .find(), .substr(), operatorul +). Conceptele de palindrom și anagramă se verifică prin algoritmi specifici: compararea caracterelor simetrice, respectiv sortarea sau numărarea frecvenței caracterelor.

Definiția și implementarea șirurilor de caractere

• Un șir de caractere (string) este o structură de date fundamentală care reprezintă o secvență ordonată de caractere
• În C++, șirurile sunt implementate prin:

- Tablouri de tip char terminate cu caracterul null ('\0')

- Clasa std::string din biblioteca standard

Funcții predefinite din biblioteca <cstring>

• strlen(s) – returnează lungimea șirului (fără terminatorul null)
• strcpy(dest, src) – copiază un șir în altul
• strcat(dest, src) – concatenează șirul sursă la sfârșitul destinației
• strcmp(s1, s2) – compară lexicografic două șiruri:

- Returnează 0 dacă sunt egale

- Returnează <0 dacă s1 < s2

- Returnează >0 dacă s1 > s2

Metode utile ale clasei std::string

• .length() și .size() – returnează lungimea șirului
• .find() – caută un subșir în șir
• .substr() – extrage un subșir
• Operatorul + – pentru concatenare
• Operatori de comparație – pentru compararea șirurilor

Prelucrări uzuale ale șirurilor de caractere

• Parcurgerea caracter cu caracter
• Căutarea unui subșir
• Înlocuirea unor caractere
• Eliminarea spațiilor
• Transformarea majusculelor în minuscule

Palindrom

• Definiție: Un șir care se citește la fel de la stânga la dreapta și de la dreapta la stânga (ex: "capac", "12321")
• Algoritm de verificare:

- Se compară primul cu ultimul caracter, apoi al doilea cu penultimul etc.

- Se ignoră eventualele spații sau semne de punctuație

- Pentru eficiență, se folosește un algoritm cu doi indici (left, right)

• Exemplu: Se citește un cuvânt s. Se determină lungimea n = strlen(s). Se parcurge cu i de la 0 la n/2-1 și se compară s[i] cu s[n-1-i]. Dacă toate perechile sunt egale, cuvântul este palindrom.

- Cod: int palindrom = 1; for(int i=0; i<strlen(s)/2; i++) if(s[i] != s[strlen(s)-1-i]) { palindrom = 0; break; }

Anagrame

• Definiție: Un cuvânt sau frază obținut prin rearanjarea literelor unui alt cuvânt (ex: "ram" și "mar")
• Metode de verificare:

- Sortarea caracterelor fiecărui șir și compararea rezultatelor

- Vectorul de frecvență – se numără frecvența fiecărui caracter (folosind un vector de 26 de elemente pentru litere mici)

• Exemplu: Se citesc două cuvinte s1 și s2. Se creează un vector de frecvență frecv[26] inițializat cu 0. Se parcurge s1 și se incrementează frecv[s1[i]-'a']; se parcurge s2 și se decrementează frecv[s2[i]-'a']. La final, dacă toate valorile din frecv sunt 0, cuvintele sunt anagrame. Atenție: cuvintele trebuie să aibă aceeași lungime.

Prelucrare cu std::string – exemplu

• Se citește o propoziție. Să se înlocuiască toate aparițiile substringului "abc" cu "xyz".
• Rezolvare: se folosește funcția find() într-un while:

- size_t pos = 0; while ((pos = s.find("abc", pos)) != string::npos) { s.replace(pos, 3, "xyz"); pos += 3; }

Verifică-te!

1. Ce returnează funcția strcmp(s1, s2) atunci când s1 este mai mic lexicografic decât s2?
2. Cum se verifică eficient dacă un șir este palindrom, folosind doi indici?
3. Ce condiție suplimentară trebuie îndeplinită de două cuvinte pentru a putea fi anagrame, înainte de a aplica algoritmul cu vector de frecvență?