De ce contează?
Ai în mână un cuvânt scris pe un șir de cărămizi, fiecare cărămidă cu o literă. Ca să verifici fiecare literă, nu sari aiurea printre ele: pui degetul pe prima cărămidă și aluneci spre dreapta, una câte una, până se termină rândul. Exact așa parcurgi un șir de caractere — literă cu literă, de la stânga la dreapta.
Intuiția
Un șir de caractere (un string) nu e ceva exotic: e pur și simplu un vector de caractere, numerotate de la 0. Cuvântul "ALGO" stă în memorie ca patru căsuțe — s[0]='A', s[1]='L', s[2]='G', s[3]='O'.
Dacă știi deja să parcurgi un vector cu un for, știi și să parcurgi un șir: faci exact același lucru, doar că în loc de numere ai litere. Plimbi un index i de la 0 până la ultima poziție și, la fiecare pas, te uiți la s[i].
Vezi cum funcționează
Folosește ← și → ca să pășești prin șir caracter cu caracter, sau Redă pentru animație. Urmărește cum indexul i avansează și cum se citește mereu doar elementul de pe poziția curentă.
Prima idee: „accesez caracterele pe ghicite". Scriu s[0], s[1], s[2]... și mă opresc când cred eu că s-a terminat cuvântul.
Problema e că trebuie să știi exact unde se termină șirul. Dacă ghicești greșit lungimea, citești dincolo de cuvânt — la un char[] acolo stă terminatorul de sfârșit de șir, iar după el e memorie nedefinită, deci citești gunoi sau ieși din șir. Cu o lungime greșită fie ratezi ultima literă, fie procesezi caractere care nu există.
Nu ghici lungimea — întreab-o pe șir. Un string știe câte caractere are: s.size(). Atunci parcurgi sigur de la 0 la s.size() - 1 cu un singur for, iar s[i] îți dă fix al i-lea caracter.
for (int i = 0; i < s.size(); i++) și prelucrezi s[i]. Un singur index, o singură trecere, nicio ghiceală despre unde se termină.
Algoritmul pas cu pas
Hai să parcurgem "ALGO". Indexul i pleacă din 0 și avansează până la s.size() - 1 = 3. La fiecare pas privim un singur caracter:
A | L | G | O |
0 | 1 | 2 | 3 |
i |
A | L | G | O |
0 | 1 | 2 | 3 |
i |
A | L | G | O |
0 | 1 | 2 | 3 |
i |
A | L | G | O |
0 | 1 | 2 | 3 |
i |
Parcurgerea singură nu face mare lucru — puterea ei vine din ce prelucrezi la fiecare pas. Să numărăm vocalele din "ALGO". Pornim cu vocale = 0 și, la fiecare caracter, verificăm dacă e vocală:
i=0,s[0]='A'→ e vocală →vocale = 1i=1,s[1]='L'→ consoană →vocale = 1i=2,s[2]='G'→ consoană →vocale = 1i=3,s[3]='O'→ e vocală →vocale = 2
La final, vocale = 2 (literele A și O). Indiferent ce calculezi — vocale, cifre, o anumită literă — scheletul rămâne identic: un singur for de la 0 la s.size() - 1, o decizie la fiecare s[i].
Implementare C++
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s; // citim un cuvant, ex. "ALGO"
int vocale = 0;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i]; // al i-lea caracter
if (c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')
vocale++; // l-am gasit, numaram
}
cout << "Caractere: " << s.size() << "\n"; // pentru "ALGO": 4
cout << "Vocale: " << vocale << "\n"; // pentru "ALGO": 2
return 0;
}Pentru "ALGO" programul afișează Caractere: 4 și Vocale: 2. Observă tiparul: s[i] accesează caracterul de pe poziția i, exact ca la un vector, iar s.size() îți spune câte sunt — nu mai ghicești unde se termină șirul.
Dacă lucrezi cu un șir clasic în stil C (char s[100]), capătul îl marchează caracterul terminator '\0', iar lungimea o afli cu strlen(s) din <cstring>. La string-ul din C++ ai mereu s.size(), care e mai sigur.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Orice caz | O(n) | O(1) |
Trecem o singură dată prin cele n = s.size() caractere, iar pe lângă șirul de intrare folosim doar câteva variabile (i, vocale), indiferent de cât de lung e șirul.
Două capcane clasice la parcurgerea unui șir:
int icomparat direct cus.size().s.size()are tip unsigned, iar la șir gol comparațiai < s.size()poate da o avalanșă de avertismente, iar dacă numeri invers cuint iși condițiai >= 0ai chiar buclă infinită (ununsignednu coboară niciodată sub zero). Soluția: fie convertești(int)s.size(), fie foloseștiint n = s.size();o singură dată și compari cun.- Off-by-one la lungime. Ultimul caracter valid e pe poziția
s.size() - 1, nus.size(). Dacă scriii <= s.size(), citești o poziție în plus, dincolo de șir — exact greșeala pe cares.size()ar trebui să o prevină.