Palindrom și anagrame la BAC: cuvinte și C++

Un cuvânt palindrom se citește la fel de la stânga la dreapta și de la dreapta la stânga. Două cuvinte sunt anagrame dacă folosesc aceleași litere cu aceleași frecvențe, eventual în altă ordine. La BAC, cele două proprietăți cer verificări diferite: palindromul compară poziții simetrice, iar anagrama compară numărul aparițiilor fiecărei litere.

Lecția privește șirurile de caractere de la matematică-informatică. Lucrăm cu două cuvinte nevide, formate numai din litere mici ale alfabetului englez. Această restricție elimină ambiguitatea privind spațiile, majusculele și diacriticele; pentru alte exerciții de BAC, regulile de normalizare trebuie citite separat.

Palindromul păstrează ordinea simetrică

În cuvântul capac, prima literă coincide cu ultima, iar a doua cu penultima. Litera din mijloc nu are nevoie de o comparație cu altă poziție. Cuvântul este palindrom.

În cuvântul carte, prima și ultima literă diferă. O singură nepotrivire este suficientă pentru răspunsul negativ. Nu trebuie să existe un anumit număr de diferențe și nici să comparăm sumele codurilor literelor.

Pentru o lungime pară, verifici toate perechile din cele două jumătăți. Pentru o lungime impară, caracterul central rămâne pe loc la inversare. În ambele cazuri, sunt suficiente jumătate din comparațiile pe care le-ai face parcurgând toate pozițiile.

Anagrama păstrează frecvențele

Cuvintele mare și rame au câte o apariție a literelor a, e, m și r. Sunt anagrame, deși niciunul nu este palindrom. Ordinea literelor diferă, dar inventarul lor este același.

Cuvintele aab și abb folosesc aceeași mulțime de litere, însă nu sunt anagrame. În primul, a apare de două ori; în al doilea, b apare de două ori. Simplul fapt că fiecare literă dintr-un cuvânt apare și în celălalt nu este suficient.

Proprietate	Ce verifici	Ce nu este suficient
Palindrom	Egalitatea perechilor simetrice	Aceleași litere fără ordine
Anagrame	Frecvențe egale pentru fiecare literă	Doar lungimi egale
Cuvinte egale	Același caracter pe fiecare poziție	Doar frecvențe egale

Două cuvinte egale sunt anagrame în sensul matematic al definiției folosite aici. Dacă o cerință exclude identitatea și cere o rearanjare diferită, trebuie adăugată explicit și condiția că textele nu coincid.

Program C++ cu două verificări independente

Programul citește două cuvinte, fiecare pe o linie separată, cu lungimi între unu și o sută. Afișează pe prima linie dacă primul cuvânt este palindrom și pe a doua dacă cele două cuvinte sunt anagrame. Alfabetul de intrare este garantat de enunț.

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char a[101], b[101];
    cin.getline(a, 101);
    cin.getline(b, 101);
    int n = int(strlen(a));
    int m = int(strlen(b));
    bool palindrom = true;
    for (int i = 0; i < n / 2; ++i)
        if (a[i] != a[n - 1 - i])
            palindrom = false;
    int diferenta[26] = {};
    for (int i = 0; i < n; ++i)
        ++diferenta[a[i] - 'a'];
    for (int i = 0; i < m; ++i)
        --diferenta[b[i] - 'a'];
    bool anagrame = (n == m);
    for (int i = 0; i < 26; ++i)
        if (diferenta[i] != 0)
            anagrame = false;
    cout << (palindrom ? "DA" : "NU") << '\n';
    cout << (anagrame ? "DA" : "NU");
    return 0;
}

Tabloul de diferențe adună aparițiile din primul cuvânt și scade aparițiile din al doilea. O valoare pozitivă înseamnă un surplus în primul cuvânt, iar una negativă un surplus în al doilea. Toate valorile trebuie să fie zero pentru egalitatea frecvențelor.

Urmărirea frecvențelor pentru litere repetate

Pentru aab și aba, după primul cuvânt avem două apariții ale lui a și una a lui b. Scăderea literelor celui de-al doilea cuvânt anulează exact aceste valori. Rezultatul este zero pe toate pozițiile, deci cuvintele sunt anagrame.

Pentru aab și abb, diferența pentru a este unu, iar pentru b este minus unu. Suma diferențelor este tot zero, deoarece lungimile sunt egale, dar fiecare diferență nu este zero. Acest exemplu arată de ce verificarea unui singur total este insuficientă.

Nici suma codurilor caracterelor nu identifică sigur inventarul literelor. De exemplu, în ASCII, cuvintele ad și bc au aceeași sumă a codurilor și aceeași lungime, dar nu sunt anagrame. Frecvențele păstrează informația pe care totalul o pierde.

Relația dintre cele două proprietăți

Orice cuvânt și inversul său sunt anagrame, pentru că inversarea nu adaugă și nu elimină litere. Totuși, un cuvânt este palindrom numai dacă inversul coincide cu el pe fiecare poziție.

De exemplu, ab și ba sunt anagrame, dar primul cuvânt nu este palindrom. Cuvântul aba este palindrom și este anagramă cu aab, deși al doilea nu este palindrom. Răspunsurile celor două verificări trebuie păstrate separat.

O rearanjare poate forma un palindrom doar dacă cel mult o literă are frecvență impară. Motivul este că pozițiile din afara centrului se grupează în perechi egale. Aceasta este o proprietate despre posibilitatea rearanjării, nu o dovadă că ordinea actuală este deja palindromică.

Ce faci cu majusculele și spațiile

Dacă enunțul cere ignorarea diferenței dintre majuscule și minuscule, normalizezi literele înaintea comparațiilor. Altfel, A și a sunt caractere diferite în reprezentarea obișnuită și trebuie tratate conform cerinței.

Pentru expresii formate din mai multe cuvinte, trebuie să știi dacă spațiile și punctuația participă la proprietate. Nu elimina automat aceste caractere doar pentru că ai întâlnit anterior un exemplu de palindrom lingvistic care le ignora.

Programul prezentat folosește fiecare literă drept indice într-un tablou cu douăzeci și șase de poziții. Introducerea unui caracter din afara alfabetului declarat ar încălca ipoteza acestui acces. Verificarea alfabetului sau normalizarea sunt etape distincte, dacă enunțul le face necesare.

Eficiență și memorie

Verificarea palindromului are timp proporțional cu lungimea primului cuvânt și folosește un număr constant de variabile suplimentare. Nu construim inversul cuvântului, deoarece perechile pot fi comparate direct.

Verificarea anagramelor parcurge ambele cuvinte și apoi alfabetul fix. Timpul este proporțional cu suma lungimilor, iar tabloul auxiliar are dimensiune constantă pentru alfabetul ales. Sortarea ar fi o alternativă, dar nu este necesară pentru această cerință.

Explică de ce fiecare poziție din tablou reprezintă o literă și de ce zero înseamnă echilibru. Această legătură dintre reprezentare și proprietate susține învățarea prin înțelegere.

Exerciții cu răspunsuri

Primul cuvânt este capac, iar al doilea accap. Primul este palindrom și cele două sunt anagrame. Frecvențele sunt două pentru c, două pentru a și una pentru p.

Cuvintele sunt ab și ba. Primul nu este palindrom, dar perechea este formată din anagrame.

Cuvintele sunt aab și abb. Primul nu este palindrom și cuvintele nu sunt anagrame. Lungimea egală nu compensează frecvențele diferite.

Cuvântul este a. Este palindrom. Nu există nicio pereche de poziții distincte care să contrazică proprietatea.

Întrebări frecvente

Dacă toate frecvențele sunt pare, cuvântul este palindrom?

Nu neapărat. Cuvântul aabb are frecvențe pare, dar nu este palindrom în ordinea dată. Poate fi rearanjat ca abba, care este palindrom.

De ce nu compar toate pozițiile la palindrom?

Fiecare pereche ar fi verificată de două ori. Jumătate din poziții acoperă toate perechile distincte; caracterul central, dacă există, este egal cu el însuși.

Cum verific dacă am amestecat proprietățile?

Testează separat o pereche de anagrame fără palindrom și un palindrom cu un cuvânt care nu îi este anagramă. Pentru feedback pe soluție, poți consulta un profesor de informatică.