Probleme simple cu șiruri de caractere în C++

Într-un articol mai vechi am vorbit despre cum funcționează șirurile de caractere în C++. Astăzi voi rezolva câteva probleme elementare cu șiruri de caractere, ce folosesc funcțiile din biblioteca <cstring>. Majoritatea problemelor se pot găsi pe PbInfo.

Problema 1.

Se dă un șir de caractere ce conține numai litere mici ale alfabetului englez și spații. Să se determine câte vocale din șir sunt cuprinse între două consoane.

Ca să verificăm dacă un caracter este vocală putem face un test cu cinci cazuri: if (chr == 'a' || chr == 'e' || chr == 'i' || chr == 'o' || chr == 'u'). Însă, un if mai elegant arată așa: if (strchr("aeiou", chr)). Acesta testează dacă pointer-ul returnat de funcția strchr este nenul, deci dacă chr apare în șirul "aeiou". Dacă da, atunci chr clar este o vocală.

Deci, pur și simplu parcurgem șirul str, începând cu poziția 2, și verificăm la fiecare pas i dacă str[i - 2] și str[i] sunt consoane, iar str[i - 1] este vocală. Dacă da, incrementăm soluția.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
int cnt;
char str[SMAX];

int main() {
    cin >> str;
    for (int i = 2; str[i]; i++)
        cnt += (
            !strchr("aeiou", str[i - 2]) &&
             strchr("aeiou", str[i - 1]) &&
            !strchr("aeiou", str[i    ])
        );
    cout << cnt << '\n';
    return 0;
}

Un detaliu important la această sursă este modul în care am parcurs string-ul, mai exact condiția din for: str[i]. Prin asta se testează dacă valoarea str[i] este nenulă. Ea devine zero abia când am ajuns la finalul șirului de caractere, adică atunci când str[i] == '\0'. Acesta este modul eficient și elegant de a parcurge un șir de caractere. Mulți profesori de info, inclusiv cei care propun subiectele pentru bac, parcurg șirurile de caractere așa:

for (int i = 0; i < strlen(str); i++)

(Mă rog, ei nici nu declară i-ul local în for, dar asta e altă poveste.) Parcurgerea asta are complexitatea $O(n^2)$ pentru că la fiecare pas se apelează funcția strlen, care pentru a determina lungimea lui str, este nevoită să-l parcurgă în întregime, până ajunge la terminatorul nul.

Problema 2.

Se dă o propoziție care conține numai litere mici ale alfabetului englez și spații. Să se afișeze cuvintele din propoziție care conțin numai vocale.

String-ul nostru poate conție spații, motiv pentru care trebuie citit cu cin.getline. Dacă citirea s-ar fi făcut din fișier, am fi putut citi propoziția cuvânt cu cuvânt, folosind while (fin >> str). Dar chiar și în cazul ăla, varianta preferată la bac este getline. După ce am citit șirul de caractere, îl împărțim pe cuvinte folosind strtok, iar pentru fiecare cuvânt testăm dacă este format doar din vocale. Pentru asta am definit o funcție check, de tip bool, ce primește ca parametru un șir de caractere.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

bool check(char* str) {
    for (int i = 0; str[i]; i++)
        if (!strchr("aeiou", str[i]))
            return false;
    return true;
}

int main() {
    cin.getline(str, SMAX);
    char *ptr = strtok(str, " ");
    while (ptr) {
        if (check(ptr))
            cout << ptr << '\n';
        ptr = strtok(NULL, " ");
    }
    return 0;
}

Cine a înțeles bine pointerii, ar trebui să știe de ce apelul check(ptr) funcționează.

Problema 3.

Se dă un șir de caractere ce conține numai litere ale alfabetului englez și spații. Să se înlocuiască literele mari cu litere mici și vice-versa.

Din nou, citim șirul de caractere folosind cin.getline. Îl parcurgem caracter cu caracter, iar când dăm de o literă, o schimbăm din minusculă în majusculă sau invers, după caz. De exemplu, pentru a transforma o literă mică în literă mare, scădem din ea valoarea 'a', obținând poziția literei în alfabet. Apoi, adăugăm 'A', pentru a obține litera mare corespunzătoare poziției respective.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

int main() {
    cin.getline(str, SMAX);
    for (int i = 0; str[i]; i++)
        if ('a' <= str[i] && str[i] <= 'z')
            str[i] += 'A' - 'a';
        else if ('A' <= str[i] && str[i] <= 'Z')
            str[i] += 'a' - 'A';
    cout << str << '\n';
    return 0;
}

Problema 4.

Se dă o propoziție formată din litere mici ale alfabetului englez, spații și semnele de punctuație virgulă și punct. Determinați un cuvânt palindrom din propoziție, primul în ordine alfabetică. Se garantează că există cel puțin un cuvânt palindrom în propoziția dată.

La fel ca la problema 2, citim șirul cu cin.getline și îl împărțim pe cuvinte cu strtok (de data asta șirul de separatori este " ,."). Din nou, am definit o funcție check care testează dacă un șir de caractere îndeplinește proprietatea dată, și anume dacă este palindrom. Funcția constă în parcurgerea șirului cu doi indici i și j (i crește și j descrește) cât timp str[i] == str[j]. Problema ne cere cel mai mic cuvânt palindrom din punct de vedere lexicografic, așa că la fiecare pas testăm dacă avem un nou candidat la soluție !ans[0] || strcmp(ptr, ans) < 0. Inițial, ans conține string-ul nul, adică ans[0] == '\0'.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX], ans[SMAX];

bool check(char* str) {
    for (int i = 0, j = strlen(str) - 1; i < j; i++, j--)
        if (str[i] != str[j])
            return false;
    return true;
}

int main() {
    cin.getline(str, SMAX);
    char *ptr = strtok(str, " ,.");
    while (ptr) {
        if (check(ptr) && (!ans[0] || strcmp(ptr, ans) < 0))
            strcpy(ans, ptr);
        ptr = strtok(NULL, " ,.");
    }
    cout << ans << '\n';
    return 0;
}

Problema 5.

Se dă un șir de caractere ce conține numai litere mici ale alfabetului englez. Să se afișeze literele care apar de exact două ori în șirul dat.

Probabil soluția cea mai clară și mai eficientă este să folosim un vector de frecvență, însă vreau să arăt un mod interesant de a utiliza funcția strchr. Pentru fiecare dintre cele 26 de litere posibile verificăm dacă are frecvența 2 astfel: Verificăm dacă strchr(str, chr) returnează un pointer nenul. Dacă nu, frecvența lui chr e 0. Dacă da, salvăm acest pointer în pt1, și facem din nou strchr, dar de data asta de la poziția pt1 + 1. Dacă funcția ne returnează pointer-ul nul, înseamnă că frecvența lui chr e 1. În caz contrar, facem un ultim strchr de la poziția pt2 + 1. Dacă nu l-am mai găsit pe chr, înseamnă că frecvența e 2. Altfel, chr apare de mai mult de două ori în str.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

bool check(char chr) {
    char *pt1 = strchr(str, chr);
    if (!pt1)
        return false;
    char *pt2 = strchr(pt1 + 1, chr);
    if (!pt2)
        return false;
    return !strchr(pt2 + 1, chr);
}

int main() {
    cin >> str;
    for (char chr = 'a'; chr <= 'z'; chr++)
        if (check(chr))
            cout << chr << '\n';
    return 0;
}

Problema 6.

Se dă un șir de caractere format din mai multe cuvinte, separate prin spații. Cuvintele pot conține atât litere mici, cât și litere mari ale alfabetului englez. Să se afișeze acronimul acestui grup de cuvinte. De exemplu, pentru "Cash rules everything around me", se va afișa "CREAM".

Nimic prea special aici. Împărțim șirul în cuvinte folosind strtok, iar pentru fiecare cuvânt ptr afișăm prima sa literă (ptr[0]), eventual transformată în majusculă.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

int main() {
    cin.getline(str, SMAX);
    char *ptr = strtok(str, " ");
    while (ptr) {
        cout << (char) ('a' <= ptr[0] && ptr[0] <= 'z' ? ptr[0] + 'A' - 'a' : ptr[0]);
        ptr = strtok(NULL, " ");
    }
    cout << '\n';
    return 0;
}

Problema 7.

Să se scrie un program care să afişeze prefixele şi sufixele unui cuvânt citit.

Sufixele se afișează ușor, deoarece sufixului care începe la poziția i îi corespunde șirul (str + i). Nici prefixele nu sunt foarte greu de afișat. Dacă vrem să afișăm prefixul care se termină la poziția i, punem '\0' pe str[i + 1], îl afișăm pe str (care acum se termină în i) iar apoi punem înapoi pe str[i + 1] caracterul inițial de la poziția respectivă. Desigur, puteam afișa sufixele și prefixele caracter cu caracter prin câte un for, dar n-ar fi avut același farmec.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

int main() {
    cin >> str;
    for (int i = strlen(str); i >= 1; i--) {
        char chr = str[i];
        str[i] = '\0';
        cout << str << '\n';
        str[i] = chr;
    }
    for (int i = 0; str[i]; i++)
        cout << (str + i) << '\n';
    return 0;
}

Problema 8.

Să se scrie un program care citeşte un şir de caractere format din litere mici ale alfabetului englez şi elimină din șir toate vocalele.

Parcurgem șirul, iar dacă la poziția i am găsit o vocală, o ștergem astfel: Copiem într-un string auxiliar subșirul care începe la poziția i + 1 (str + i + 1), iar apoi copiem șirul aux în (str + i). Puteam copia direct str + i + 1 în str + i, însă nu e recomandat. Conform documentației oficiale C++, apelul funcției strcpy pentru șiruri ce se suprapun poate duce la undefined behaviour. Oricum complexitatea e aceeași; dacă chiar ne interesa eficiența, puteam rezolva toată problema în timp liniar inserând într-un șir aux fiecare consoană din str, urmând să-l copiem pe aux în str. După ce am efectuat această copiere, trebuie să-l decrementăm pe i, pentru a nu sări peste litera ce tocmai a înlocuit vocala ștearsă.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX], aux[SMAX];

int main() {
    cin >> str;
    for (int i = 0; str[i]; i++)
        if (strchr("aeiou", str[i])) {
            strcpy(aux, str + i + 1);
            strcpy(str + i, aux);
            i--;
        }
    cout << str << '\n';
    return 0;
}

Problema 9.

Se dau două șiruri de caractere ce conțin doar litere mici ale alfabetului englez. Să se determine de câte ori apare al doilea șir în primul, precum și pozițiile la care apare acesta.

Folosim funcția strstr într-un mod similar celui în care folosim strtok. Ținem într-un pointer ptr poziția ultimei apariții a celui de-al doilea șir în primul. Cât timp ptr nu e NULL, inserăm în vectorul ans valoarea ptr - a (distanța dintre pointerii ptr și a, adică poziția propriu-zisă a apariției), și căutăm următoarea apariție a lui b în a. Pe aceasta o căutăm de la ptr + 1, deci ptr devine strstr(ptr + 1, b).

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char a[SMAX], b[SMAX];

int cnt;
int ans[SMAX];

int main() {
    cin >> a >> b;
    char *ptr = strstr(a, b);
    while (ptr) {
        ans[cnt++] = ptr - a;
        ptr = strstr(ptr + 1, b);
    }

    cout << cnt << '\n';
    for (int i = 0; i < cnt; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

Problema 10.

Se dă o propoziție care conține litere ale alfabetului englez, spații și semne de punctuație. Să se afișeze, pe linii separate, fiecare cuvânt și frecvența lui în șirul dat. Cuvintele se vor afișa în ordine lexicografică.

Partea cu strtok e simplă, problema este cum putem reține cuvintele ca să le sortăm ușor. Desigur, a sorta ușor înseamnă a putea folosi funcția sort din STL. Dacă folosim o matrice cu elemente de tip char, astfel încât fiecare linie să conțină un cuvânt, n-am putea folosi sort, căci funcția s-ar apela practic pentru un vector cu elemente de tipul const char* (pointeri constanți), care nu pot fi interschimbați, tocmai pentru că sunt constanți. Putem rezolva asta definind un struct Word care să conțină un câmp str care să rețină string-ul propriu-zis. Acum swap-urile din funcția sort se vor putea produce fără probleme, pentru că elementele vectorului nu mai sunt constante.

Revenind la problemă, trebuie menționat că struct-ul Word va conține și un câmp frq care va reține frecvența cuvântului respectiv. Așadar, ținem un vector de cuvinte (words). De fiecare dată când întâlnim un nou cuvânt, verificăm printr-o parcurgere dacă aparține vectorului. Dacă da, incrementăm frecvența elementului corespunzător. Dacă nu, inserăm la finalul vectorului un nou element de tipul Word, în care copiem ptr-ul curent, căruia îi setăm frecvența la 1. Mai rămâne să definim criteriul de sortare. Putem face asta în multe moduri; eu am ales supraîncărcarea operatorului < pentru variabilele de tipul Word.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
char str[SMAX];

struct Word {
    int frq;
    char str[SMAX];
};

bool operator<(const Word& x, const Word& y) {
    return strcmp(x.str, y.str) < 0;
}

int cnt;
Word words[SMAX];

int main() {
    cin.getline(str, SMAX);
    char *ptr = strtok(str, " ,.");
    while (ptr) {
        int i;
        for (i = 0; i < cnt; i++)
            if (!strcmp(words[i].str, ptr)) {
                words[i].frq++;
                break;
            }
        if (i == cnt) {
            words[cnt].frq = 1;
            strcpy(words[cnt++].str, ptr);
        }
        ptr = strtok(NULL, " ,.");
    }

    sort(words, words + cnt);
    cout << cnt << '\n';
    for (int i = 0; i < cnt; i++)
        cout << words[i].str << ' ' << words[i].frq << '\n';
    return 0;
}

Problema putea fi rezolvată în câteva rânduri și mult mai eficient dacă foloseam STL, dar am ales soluția școlărească, care folosește string-uri C-style.

Problema 11.

Se dau trei șiruri de caractere a, b și c, care conțin doar litere ale alfabetului englez. Să se înlocuiască fiecare apariție a lui b în a cu c. Se garantează că nu există niciun prefix al șirului b care să fie egal cu vreun sufix de-al său; desigur, excepție face string-ul întreg.

Fără condiția asta, enunțul nu prea ar avea sens. De exemplu, dacă a = "ababa", b = "aba" și c = "c", cele două apariții ale lui b se suprapun, așa că nu este clar pe care ar trebui s-o înlocuim. Putem obține fie "cba", fie "abc".

Soluția este să folosim strstr astfel: De fiecare dată când întâlnim șirul b la adresa ptr, copiem subșirul lui a ce începe la ptr + strlen(b), adică ceea ce urmează după apariția curentă a lui b, într-un șir auxiliar aux. Apoi, copiem conținutul lui c la adresa ptr, înlocuindu-l pe b, după care îl copiem pe aux înapoi în a, la adresa ptr + strlen(c). La final, ptr devine strstr(ptr + strlen(c), b), sărind peste copia lui c proaspăt adăugată. Dacă am scrie strstr(ptr + 1, b), am intra în ciclu infinit când b este subșir al lui c (mai exact al lui c + 1), pentru că am tot face replace pe șirul nou adăugat la a.

#include <bits/stdc++.h>
using namespace std;

const int SMAX = 618;
int lenB, lenC;
char a[SMAX], b[SMAX], c[SMAX], aux[SMAX];

int main() {
    cin >> a >> b >> c;
    lenB = strlen(b);
    lenC = strlen(c);

    char *ptr = strstr(a, b);
    while (ptr) {
        strcpy(aux, ptr + lenB);
        strcpy(ptr, c);
        strcpy(ptr + lenC, aux);
        ptr = strstr(ptr + lenC, b);
    }
    cout << a << '\n';
    return 0;
}

Dacă aveți vreo problemă cu șiruri de caractere care nu vă iese, lăsați un comentariu mai jos pentru a vă ajuta