Separarea cuvintelor la BAC: spații și parcurgere

Separarea cuvintelor dintr-un text începe cu o definiție a separatorului. La BAC, nu trebuie să presupui că orice spațiu produce un cuvânt nou sau că textul începe direct cu o literă. Mai multe spații consecutive, spațiile de la margini și linia vidă schimbă rezultatul unui algoritm care numără mecanic separatorii.

Lecția se adresează conținuturilor despre șiruri de caractere de la matematică-informatică. În problema noastră, textul conține numai litere mici ale alfabetului englez și spații obișnuite. Un cuvânt este o secvență maximală de litere consecutive. Dacă un subiect de BAC definește și alte separatoare, adaptezi condiția înainte să refolosești schema.

De ce spațiile plus unu nu este o regulă generală

Pentru textul ana are mere, două spații separă trei cuvinte. Aici numărul spațiilor plus unu produce răspunsul corect. Formula funcționează însă numai sub ipoteze suplimentare: text nevid, fără spații la margini și cu exact un spațiu între cuvinte.

Textul ana are are două spații consecutive, dar numai două cuvinte. Un text alcătuit exclusiv din trei spații nu are niciun cuvânt. În ambele situații, formula simplificată eșuează pentru că numără separatoare individuale în locul grupurilor de litere.

O soluție robustă detectează intrarea într-un cuvânt. Aceasta se produce atunci când întâlnim o literă după începutul textului sau după un separator. Nu se produce la fiecare literă și nici la fiecare spațiu.

Două stări suficiente

Putem descrie parcurgerea prin două stări: în afara unui cuvânt și în interiorul unui cuvânt. La început suntem în afara unui cuvânt. Un spațiu păstrează sau restabilește această stare.

Când apare o literă și eram în afara unui cuvânt, începe un cuvânt nou. Incrementăm numărul cuvintelor și trecem în interior. Următoarele litere aparțin aceluiași cuvânt până la primul separator sau până la terminator.

Stare înainte	Caracter curent	Acțiune
În afară	Spațiu	Rămâi în afară
În afară	Literă	Începe un cuvânt și numără-l
În interior	Literă	Continuă cuvântul
În interior	Spațiu	Încheie cuvântul

Tabelul oferă o schemă reutilizabilă pentru numărare. Pentru extragerea efectivă, mai trebuie să păstrezi începutul și lungimea fiecărui cuvânt, astfel încât să poți afișa secvența corespunzătoare.

O parcurgere care extrage cuvintele

În programul următor, ignorăm mai întâi spațiile. Când ajungem la o literă, memorăm începutul cuvântului și avansăm până la spațiu sau terminator. Diferența dintre poziția finală și început este lungimea cuvântului.

Programul citește o linie cu cel mult două sute de caractere. Afișează fiecare cuvânt pe o linie separată, apoi numărul cuvintelor și lungimea maximă. Pentru un text fără cuvinte, cele două rezultate numerice sunt zero.

#include <iostream>
using namespace std;

int main() {
    char s[201];
    cin.getline(s, 201);
    int i = 0, numar = 0, maxim = 0;
    while (s[i] != '\0') {
        while (s[i] == ' ') ++i;
        if (s[i] == '\0') break;
        int inceput = i;
        while (s[i] != '\0' && s[i] != ' ') ++i;
        int lungime = i - inceput;
        ++numar;
        if (lungime > maxim) maxim = lungime;
        for (int j = inceput; j < i; ++j)
            cout << s[j];
        cout << '\n';
    }
    cout << numar << ' ' << maxim;
    return 0;
}

Bucla care ignoră spațiile nu trece de terminator, deoarece acesta nu este un spațiu. Verificarea imediat următoare împiedică tratarea sfârșitului textului ca început al unui cuvânt gol.

Exemplu urmărit pe poziții

Pentru textul ana are mere , primele două poziții sunt ignorate. Cuvântul ana începe la indicele doi și are lungimea trei. Următorul grup de spații este ignorat integral, fără să creeze cuvinte suplimentare.

Cuvântul are începe la indicele opt, iar mere la indicele doisprezece. Lungimile sunt trei, trei și patru. Programul afișează trei cuvinte, iar lungimea maximă este patru.

Spațiile finale sunt parcurse până la terminator. După ele nu începe un cuvânt nou. Această etapă este tocmai cea omisă de multe soluții care presupun că orice grup de separatori trebuie urmat de text.

Sfârșitul textului este și sfârșit de cuvânt

Ultimul cuvânt nu trebuie urmat obligatoriu de un spațiu. Terminatorul încheie textul și, implicit, orice cuvânt aflat în desfășurare. Condiția buclei interioare verifică ambele posibilități.

Dacă verifici doar spațiul, un ultim cuvânt fără separator final poate determina continuarea parcurgerii dincolo de text. Dacă prelucrezi un cuvânt numai când vezi spațiul următor, ultimul cuvânt poate fi omis din rezultat.

O metodă bună de control este să compari două texte: unul care se termină imediat după ultima literă și același text cu câteva spații adăugate la final. Numărul cuvintelor și lungimea maximă trebuie să rămână aceleași.

Ce faci cu punctuația

Programul are un alfabet de intrare explicit. Dacă adaugi virgule și puncte fără să modifici regula, acestea ar fi tratate drept părți ale secvențelor dintre spații. Rezultatul nu ar corespunde automat unei definiții lingvistice a cuvântului.

Într-o altă problemă, poți defini drept separator orice caracter care nu este literă. Atunci condiția de ignorare și condiția de continuare trebuie actualizate împreună. Nu este suficient să modifici doar una dintre ele.

Enunțul poate considera cratima parte din cuvânt sau separator. Ambele variante pot apărea în exerciții construite diferit. Algoritmul trebuie să respecte convenția cerută, nu o regulă inventată după primul exemplu.

Copierea unui cuvânt într-un alt șir

Pentru afișare, am folosit direct intervalul din textul inițial. Dacă trebuie să memorezi cuvântul separat, copiezi caracterele sale într-un tablou suficient de mare și adaugi terminatorul după ultima literă.

Lungimea cuvântului nu include terminatorul, dar capacitatea necesară îl include. Un cuvânt de două sute de litere cere cel puțin două sute unu elemente în reprezentarea folosită.

Nu modifica textul inițial prin inserarea unor terminatori între cuvinte decât dacă accepți această schimbare și știi cum vei continua parcurgerea. Pentru început, păstrarea indicilor face mai ușor de urmărit relația dintre secvență și text.

Eficiența parcurgerii

Indicele principal avansează numai spre dreapta. Fiecare caracter este inspectat într-un număr limitat de operații, iar fiecare literă este afișată o dată. Timpul este proporțional cu lungimea textului.

Nu există o parcurgere completă nouă pentru fiecare cuvânt. Deși programul conține bucle în interiorul altei bucle, limitele lor sunt legate de secvențe disjuncte ale aceluiași text. Numărarea operațiilor reale este mai utilă decât numărarea nivelurilor de indentare.

Această analiză ilustrează diferența dintre memorarea unei forme de cod și înțelegerea ei. Urmărește cât de des poate fi vizitat fiecare caracter, nu doar câte instrucțiuni repetitive vezi.

Exerciții cu răspunsuri

Textul este bac. Există un singur cuvânt, cu lungimea trei. Lipsa spațiilor nu înseamnă lipsa cuvintelor.

Textul conține numai cinci spații. Numărul cuvintelor și lungimea maximă sunt zero. Nu se afișează linii pentru cuvinte inexistente.

Textul este a bb ccc. Numărul cuvintelor este trei și lungimea maximă este trei. Fiecare cuvânt este extras exact o dată.

Întrebări frecvente

Pot avea un cuvânt de lungime zero?

Nu în definiția folosită aici. Grupurile de spații sunt separatoare, iar o secvență de cuvânt începe numai după întâlnirea unei litere.

Bucla interioară face algoritmul pătratic?

Nu în această implementare. Indicele nu revine la început pentru fiecare cuvânt, iar intervalele extrase nu se suprapun. Numărul total de caractere parcurse rămâne proporțional cu lungimea textului.

Cum verific o cerință cu alte separatoare?

Scrie întâi mulțimea separatorilor, apoi testează textul vid, separatorii consecutivi și ultimul cuvânt fără separator final. Pentru corectarea unei soluții poți consulta anunțurile profesorilor de informatică.