Opis glavnog rešenja

Direktan pristup sastoji se u poređenju svake niske sa svakom drugom: poređenje dve niske maksimalne dužine \(m\) karakter po karakter je u najgorem slučaju složenosti \(O(m)\). Ukupan broj poređenja niski je reda \(O(n^2)\), te je ukupna složenost odgovarajućeg algoritma \(O(n^2m)\).

Efikasnije rešenje dobija se sortiranjem svih niski i traženjem duplikata u sortiranom nizu. Sortiranje niski uključuje \(O(n \log n)\) upoređivanja niski, a svako poređenje niski je u najgorem slučaju složenosti \(O(m)\), te je ukupna složenost sortiranja niski jednaka \(O(nm \log n)\). Dodatno, prolazak kroz skup niski u sortiranom redosledu i identifikovanje istih niski je složenosti \(O(nm)\), te je ukupna složenost ovog algoritma \(O(nm \log n)\).

Pristup zasnovan na heširanju niski redukuje vreme poređenja dve niske na \(O(1)\), pod pretpostavkom da ne proveravamo da li je došlo do kolizije. Na taj način dobijamo algoritam složenosti \(O(nm + n \log n)\), gde složenost \(O(nm)\) potiče od računanja heš-vrednosti svih niski, a \(O(n \log n)\) od sortiranja niski na osnovu njihovih heš-vrednosti. Dodatno, prolazak kroz heš-vrednosti niski u sortiranom poretku i identifikovanje istih niski je složenosti \(O(n)\).

Ako želimo da budemo sigurni u ispravnost algoritma, kada su heš-vrednosti nekih niski jednake, možemo eksplicitno uporediti te niske. U najgorem slučaju, kada su sve heš-vrednosti jednake, potrebno je \(n^2\) poređenja niski, koja zahtevaju vreme \(O(m)\), što zahteva dodatno vreme \(O(n^2m)\). Međutim, realno je očekivati da su grupe jednakih heš-vrednosti mnogo manje i da će ovo vreme biti mnogo manje. Još bolje od toga, možemo elemente svake grupe zasebno leksikografski sortirati i zatim porediti uzastopne niske.

U implementaciji se ne proverava postojanje kolizija, tj. pretpostavlja se da jednakim heš-vrednostima odgovaraju jednake niske. Implementacija dodatne faze u kojoj bi se izvršilo direktno poređenje niski unutar svake grupe i dodatno razdvajanje grupe na podgrupe ako se utvrdi da sadrži različite niske prepušta se čitaocu.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int kod(char c) {
    return c - 'a' + 1;
}

long long izracunajHesVrednost(const string& s) {
    int p = 31;
    int m = 1e9 + 9;
    int n = s.size();

    long long h = 0;

    for (int i = 0; i < n; i++) {
        h = (h * p + kod(s[i])) % m;
    }

    return h;
}

vector<vector<int>> grupisiIsteNiske(const vector<string>& niske) {
    int n = niske.size();

    vector<pair<long long, int>> h(n);

    for (int i = 0; i < n; i++) {
        h[i] = {izracunajHesVrednost(niske[i]), i + 1};
    }

    sort(h.begin(), h.end());

    vector<vector<int>> grupe;

    for (int i = 0; i < n; i++) {
        if (i == 0 || h[i].first != h[i - 1].first) {
            vector<int> novaGrupa;
            grupe.push_back(novaGrupa);
        }

        grupe.back().push_back(h[i].second);
    }

    return grupe;
}

int main() {
    int n;
    cin >> n;

    vector<string> niske(n);

    for (int i = 0; i < n; i++) {
        cin >> niske[i];
    }

    vector<vector<int>> grupe = grupisiIsteNiske(niske);

    for (const auto& grupa : grupe) {
        for (int indeks : grupa) {
            cout << indeks << ' ';
        }
        cout << '\n';
    }

    return 0;
}