Verificarea anagramelor cu frecvențe în C++

Două cuvinte sunt anagrame dacă au aceleași litere, fiecare de același număr de ori, indiferent de ordine. mare și rame sunt anagrame. aab și abb nu sunt, deși folosesc aceleași litere distincte.

Un alfabet bine definit

Citim două linii, fiecare cu cel mult 1000 de litere mici din alfabetul latin a..z, fără spații sau diacritice. Acceptăm și linii goale pentru a testa cazul limită. Afișăm DA sau NU. Această restricție este esențială: formula caracter-'a' produce un indice valid numai pentru alfabetul ales.

Șirurile clasice au capacitatea 1001: până la 1000 de caractere utile și terminatorul \0. Vectorul de frecvențe are 26 de poziții, câte una pentru fiecare literă. Nu confundăm capacitatea rezervată cu lungimea textului citit.

Cuvintele aab și aba au câte două litere a și una b; aab și abb au frecvențe diferite.Mărește schema ↗

Diferența frecvențelor

Adăugăm câte unu pentru fiecare literă din primul șir și scădem câte unu pentru fiecare literă din al doilea. La final, toate pozițiile trebuie să fie zero. Pentru aab și aba, diferențele finale pentru a și b sunt ambele zero. Pentru aab și abb, diferența lui a este 1, iar a lui b este -1.

Nu trebuie să sortăm textele și nu trebuie să căutăm fiecare literă în celălalt cuvânt. O simplă verificare a prezenței ar pierde informația despre repetiții.

Varianta cu char[] și tablou de frecvențe

#include <iostream>
using namespace std;
int main() {
    char a[1001], b[1001];
    cin.getline(a, 1001); cin.getline(b, 1001);
    int f[26] = {};
    for(int i=0;a[i]!='\0';++i) ++f[a[i]-'a'];
    for(int i=0;b[i]!='\0';++i) --f[b[i]-'a'];
    bool egal=true;
    for(int i=0;i<26;++i) if(f[i]!=0) egal=false;
    cout << (egal ? "DA\n" : "NU\n");
}

Varianta cu std::string și std::vector

getline citește în obiectele string, iar buclele parcurg direct caracterele. Frecvențele rămân 26 de întregi inițializați cu zero. Limita didactică de 1000 de litere pe linie rămâne aceeași.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string a, b;
    getline(cin, a); getline(cin, b);
    vector<int> f(26, 0);
    for(char c : a) ++f[c-'a'];
    for(char c : b) --f[c-'a'];
    bool egal=true;
    for(int i=0;i<26;++i) if(f[i]!=0) egal=false;
    cout << (egal ? "DA\n" : "NU\n");
}

Cost și limitele modelului

Pentru lungimi p și q, timpul este O(p+q+26), iar memoria auxiliară pentru frecvențe O(26). Textul ocupă separat O(p+q). Diferențele pot fi negative, deci folosim un tip întreg cu semn.

Pentru texte românești cu diacritice, majuscule sau spații, trebuie definit întâi ce considerăm aceeași literă. Codificarea UTF-8 poate reprezenta o literă prin mai mulți octeți; nu este corect să mărești pur și simplu tabloul și să păstrezi formula de mai sus.

Exersează

Verifică abc cu cba, aab cu abb, două linii goale și un șir gol față de a. Rezultatele sunt DA, NU, DA și NU. Testul cu lungimi diferite descoperă soluțiile care verifică doar existența literelor.

Extinde problema la ignorarea spațiilor, dar păstrează alfabetul explicit. Scrie separat ce caractere elimini și de ce. Pentru comparare fără deosebire între majuscule și minuscule, normalizează fiecare literă înainte de actualizarea frecvenței.

Revezi codurile caracterelor, vectorii de frecvență și alte comparații între șiruri.

Întrebări frecvente

Ce sunt două anagrame?

Două texte cu aceleași litere și aceleași numere de apariții, indiferent de ordine. mare și rame sunt anagrame; aab și abb nu sunt, deși au aceleași litere distincte.

De ce nu ajunge să compar literele distincte ale cuvintelor?

Trebuie comparată și frecvența fiecărei litere. Un tablou cu 26 de contoare este suficient pentru alfabetul restrâns la litere mici a..z, folosit în această lecție.

Metoda cu 26 de frecvențe acceptă diacritice și majuscule?

Nu în forma prezentată. Intrarea este limitată la litere mici latine fără diacritice. Pentru alte caractere trebuie stabilite alfabetul, normalizarea și reprezentarea înainte de alegerea contoarelor.