Opis glavnog rešenja

Podniske različitih dužina ne mogu biti jednake, pa ih možemo obrađivati po dužinama. Za svaku dužinu posmatramo sve podniske te dužine i njihove heš-vrednosti ubacujemo u skup. Broj različitih heš-vrednosti za tu dužinu dodajemo na ukupan rezultat.

Da bismo heš svake podniske računali brzo, najpre računamo stepene baze i heš-vrednosti svih prefiksa. Heš podniske \(s[l..r]\) zatim dobijamo iz prefiksnih heševa u vremenu \(O(1)\). Rešenje pretpostavlja da su kolizije heš-funkcije zanemarljive.

Ako je \(n\) dužina niske, za svaku dužinu obilazimo sve podniske te dužine, pa je vremenska složenost \(O(n^2 \log n)\) zbog ubacivanja u uređeni skup. Dodatna memorija je \(O(n)\).

#include <iostream>
#include <vector>
#include <set>
#include <string>

using namespace std;

using ull = unsigned long long;

const ull P = 31;
const ull MOD = 4294967291ULL;

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

vector<ull> izracunajStepene(int n) {
    vector<ull> pStepen(n + 1);

    pStepen[0] = 1;

    for (int i = 1; i <= n; i++) {
        pStepen[i] = (pStepen[i - 1] * P) % MOD;
    }

    return pStepen;
}

vector<ull> izracunajPrefiksneHeseve(const string& s) {
    int n = s.size();

    vector<ull> h(n + 1, 0);

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

    return h;
}

ull hesPodniske(const vector<ull>& h,
                const vector<ull>& pStepen,
                int l,
                int r) {
    int len = r - l + 1;

    ull deoKojiOduzimamo = (h[l] * pStepen[len]) % MOD;

    ull rezultat = (h[r + 1] + MOD - deoKojiOduzimamo) % MOD;

    return rezultat;
}

int brojRazlicitihPodniski(const string& s) {
    int n = s.size();

    vector<ull> pStepen = izracunajStepene(n);
    vector<ull> h = izracunajPrefiksneHeseve(s);

    int brojPodniski = 0;

    for (int len = 1; len <= n; len++) {
        set<ull> heseviDuzineLen;

        for (int l = 0; l + len <= n; l++) {
            int r = l + len - 1;

            ull hTekuce = hesPodniske(h, pStepen, l, r);

            heseviDuzineLen.insert(hTekuce);
        }

        brojPodniski += heseviDuzineLen.size();
    }

    return brojPodniski;
}

int main() {
    string s;
    cin >> s;

    cout << brojRazlicitihPodniski(s) << '\n';

    return 0;
}

Rešenje iz skripte

Direktan pristup bi bio da se sve podniske ubace u skup i da se proveri broj elemenata tog skupa. Ova ideja se može optimizovati, pre svega po pitanju zauzeća memorije.

Za početak, dovoljno je porediti samo segmente istih dužina jer samo oni mogu biti međusobno jednaki. Zato, umesto korišćenja jedinstvenog skupa u koji smeštamo sve segmente, segmente možemo obrađivati u redosledu njihovih dužina i u skupu možemo istovremeno čuvati samo segmente iste dužine.

Dalje rešenje zasnovano je na heširanju, pri čemu pretpostavljamo da je heš-funkcija takva da je verovatnoća kolizije jako mala, tj. da različite podniske iste dužine uvek daju različite heš-vrednosti. Koristi se polinomijalna heš-funkcija \(h'(s) = (s[0] + s[1] \cdot p + \ldots + s[n-1] \cdot p^{n-1}) \bmod m.\)

Heš-vrednost svakog segmenta može se računati korišćenjem razlike heš-vrednosti odgovarajućih prefiksa. Umesto da računamo i poredimo tačne heš-vrednosti dva segmenta iste dužine korišćenjem modularnih multiplikativnih inverza, dovoljno je izračunati heš-vrednosti segmenata pomnožene nekim istim stepenom broja \(p\).

Dakle, prolazimo redom kroz sve moguće dužine \(l = 1, 2, \ldots, n\) segmenata niske \(s\) i konstruišemo seriju heš-vrednosti svih segmenata dužine \(l\) koji su pomnoženi nekim istim, maksimalnim stepenom broja \(p\). Broj različitih elemenata te serije, što je pod pretpostavkom da nema kolizija broj različitih segmenata dužine \(l\), možemo odrediti korišćenjem skupa. Ukupan broj različitih segmenata jednak je zbiru broja različitih segmenata dužine \(l\) u niski, za svako moguće \(l\).

Prilikom računanja proizvoda heš-vrednosti segmenta i vrednosti \(p^{n-1}\) po modulu \(m\) množe se dve vrednosti iz opsega \([0, m)\), te vrednost parametra \(m\) biramo tako da \(m \cdot m\) staje u 64-bitni ceo broj.

Operacije za rad sa uređenim skupom od \(k\) elemenata su složenosti \(O(\log k)\), a segmenata ima ukupno \(O(n^2)\), te složenost ovog algoritma iznosi \(O(n^2 \log n)\). Umetanjem heš-vrednosti u skup, umesto umetanja samih podniski u skup, značajno je smanjena memorijska složenost skupa, koja uz heširanje iznosi \(O(n)\), a bez heširanja bi iznosila \(O(n^2)\).

#include <iostream>
#include <vector>
#include <set>
#include <string>

using namespace std;

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

int brojRazlicitihPodniski(const string& s) {
    typedef unsigned long long ull;

    int p = 31;
    ull m = 4294967291ULL;
    int n = s.size();

    vector<ull> pStepen(n);

    pStepen[0] = 1;

    for (int i = 1; i < n; i++) {
        pStepen[i] = (pStepen[i - 1] * p) % m;
    }

    vector<ull> h(n + 1, 0);

    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] + (s[i] - 'a' + 1) * pStepen[i]) % m;
    }

    int brojPodniski = 0;

    for (int l = 1; l <= n; l++) {
        set<ull> heseviDuzineL;

        for (int i = 0; i <= n - l; i++) {
            ull hTekuce = (h[i + l] - h[i] + m) % m;

            hTekuce = (hTekuce * pStepen[n - i - 1]) % m;

            heseviDuzineL.insert(hTekuce);
        }

        brojPodniski += heseviDuzineL.size();
    }

    return brojPodniski;
}

int main() {
    string s;
    cin >> s;

    cout << brojRazlicitihPodniski(s) << '\n';

    return 0;
}