Egalitate de chei: compari șiruri prin amprentă

Ideea-cheie

A compara două șiruri de lungime L caracter cu caracter costă O(L) în cazul cel mai rău. Dacă faci asta de multe ori — într-o buclă peste N șiruri — ajungi rapid la O(N·L) sau chiar O(N²·L). Tentant, dar lent.

Trucul de punte: reduci fiecare șir la o cheie și lucrezi cu cheia. Cheia poate fi un număr (un hash) sau chiar șirul în sine pus într-un dicționar. Întrebarea „l-am mai văzut pe acesta?" sau „de câte ori apare?" devine atunci o căutare în unordered_set / unordered_map, adică ~O(1) amortizat per operație.

Cum alegi

Întrebarea pe care ți-o pune problema îți spune ce structură folosești. Trei tipare acoperă aproape tot:

• „L-am mai întâlnit?" → unordered_set<string>. Inserezi fiecare șir; dacă era deja înăuntru, l-ai mai văzut. Așa numeri cuvinte distincte: dimensiunea mulțimii la final.
• „De câte ori apare fiecare?" → unordered_map<string,int>. Cheia e șirul, valoarea e numărul de apariții. Un singur mp[cuvant]++ per cuvânt.
• „Care șiruri sunt anagrame între ele?" → tot un map, dar cheia nu e șirul brut. Două anagrame ("ascult" și "cultas") trebuie să primească aceeași cheie. Cheia bună: șirul cu literele sortate (ambele dau "acltsu"), sau vectorul de frecvențe al literelor. Grupezi după această cheie.

Reține criteriul: alegi cheia astfel încât exact lucrurile pe care vrei să le consideri egale să primească aceeași cheie — nici mai mult, nici mai puțin.

Iată cheia-de-anagramă în C++ — același tipar pe care îl reciclezi pentru numărat cuvinte sau grupat:

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    // grupam anagramele dintr-o lista de cuvinte
    vector<string> cuvinte = {"ascult", "cultas", "litera", "tarile", "altice"};

    // cheia = cuvantul cu literele sortate; anagramele dau aceeasi cheie
    unordered_map<string, vector<string>> grupuri;
    for (const string& c : cuvinte) {
        string cheie = c;                 // copie pe care o sortam
        sort(cheie.begin(), cheie.end()); // "ascult" -> "acltsu"
        grupuri[cheie].push_back(c);      // map compara cheia EXACT, fara coliziuni
    }

    // afisam fiecare grup de anagrame
    for (const auto& g : grupuri) {
        cout << g.first << ":";
        for (const string& c : g.second) cout << " " << c;
        cout << "\n";
    }
    // grupul "acltsu" contine: ascult cultas
    return 0;
}

Costul: sortarea unei chei de lungime L e O(L·log L), plus o căutare ~O(1) în map. Pentru N cuvinte ajungi la O(N·L·log L) — mult sub O(N²·L) pe care l-ai fi plătit comparând fiecare cuvânt cu fiecare.