Opis glavnog rešenja

Sve rotacije niske \(s\) možemo posmatrati kao podniske dužine \(n\) u niski \(ss\), koja se dobija nadovezivanjem niske \(s\) na samu sebe. Potrebno je pronaći početak leksikografski najmanje od prvih \(n\) takvih podniski.

Kada poredimo dve rotacije, tražimo najduži zajednički prefiks. Njegovu dužinu nalazimo binarnom pretragom, a jednakost prefiksa proveravamo u vremenu \(O(1)\) pomoću prefiksnih heš-vrednosti. Kada znamo dužinu zajedničkog prefiksa, naredni karakter određuje koja rotacija je leksikografski manja. Ako je zajednički prefiks dužine \(n\), rotacije su jednake.

Za svaku rotaciju proveravamo da li je manja od trenutno najbolje. Jedno poređenje traje \(O(\log n)\), pa je ukupna vremenska složenost \(O(n \log n)\). Dodatna memorija je \(O(n)\).

#include <iostream>
#include <vector>
#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;
}

bool istiPrefiks(const vector<ull>& h,
                 const vector<ull>& pStepen,
                 int i,
                 int j,
                 int len) {
    if (len == 0) {
        return true;
    }

    ull h1 = hesPodniske(h, pStepen, i, i + len - 1);
    ull h2 = hesPodniske(h, pStepen, j, j + len - 1);

    return h1 == h2;
}

int najduziZajednickiPrefiks(const vector<ull>& h,
                             const vector<ull>& pStepen,
                             int i,
                             int j,
                             int n) {
    int levo = 0;
    int desno = n;

    while (levo < desno) {
        int sredina = (levo + desno + 1) / 2;

        if (istiPrefiks(h, pStepen, i, j, sredina)) {
            levo = sredina;
        } else {
            desno = sredina - 1;
        }
    }

    return levo;
}

bool rotacijaManja(const string& ss,
                   const vector<ull>& h,
                   const vector<ull>& pStepen,
                   int i,
                   int j,
                   int n) {
    int k = najduziZajednickiPrefiks(h, pStepen, i, j, n);

    if (k == n) {
        return false;
    }

    return ss[i + k] < ss[j + k];
}

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

    string ss = s + s;

    vector<ull> pStepen = izracunajStepene(2 * n);
    vector<ull> h = izracunajPrefiksneHeseve(ss);

    int najboljiPocetak = 0;

    for (int i = 1; i < n; i++) {
        if (rotacijaManja(ss, h, pStepen, i, najboljiPocetak, n)) {
            najboljiPocetak = i;
        }
    }

    return ss.substr(najboljiPocetak, n);
}

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

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

    return 0;
}

Rešenje iz skripte

Do rešenja možemo doći tako što određujemo jednu po jednu rotaciju niske i poredimo ih leksikografski sa do tada najmanjom. Ako leksikografsko poređenje vršimo direktnim algoritmom, čija je složenost \(O(n)\) u najgorem slučaju, dobija se algoritam složenosti \(O(n^2)\). Ako su niske nasumično generisane ili sadrže tekst na prirodnom jeziku, leksikografski redosled se često može odrediti već nakon analize prvih nekoliko karaktera, pa će algoritam raditi efikasnije.

Da bi se izbeglo građenje novih niski, što je skupa operacija usled alokacije memorije, rotacije možemo dobiti tako što analiziramo sve podniske dužine \(n\) niske \(ss\) koja se dobija nadovezivanjem učitane niske \(s\) dva puta.

Leksikografsko poređenje se može ubrzati korišćenjem heširanja. Pretpostavljamo, jednostavnosti radi, da neće biti kolizija. Leksikografski redosled niski se određuje tako što se pronađe prvi karakter koji se razlikuje, tj. tako što se pronađe najduži zajednički prefiks dve niske koje se porede. On se može pronaći binarnom pretragom. U svakom koraku se ispituje jednakost nekih prefiksa dve niske koje se porede. Pošto su oni segmenti niske \(ss\), poređenje možemo izvršiti tako što izračunamo njihove heš-vrednosti, kao heš-vrednosti segmenata niske \(ss\), i uporedimo ih.

Implementacija je olakšana, jer su niske koje se porede iste dužine. Kada se nađe dužina najdužeg zajedničkog prefiksa, poredi se naredni karakter, osim u slučaju kada su niske jednake, što se lako prepoznaje jer je tada dužina zajedničkog prefiksa jednaka dužini niski koje se porede.

Pošto se binarna pretraga vrši u vremenu \(O(\log n)\), a rotacija postoji \(n\), složenost najgoreg slučaja ovog algoritma je \(O(n \log n)\). Korišćenjem naprednijih tehnika, na primer sufiksnog drveta, ovaj problem može se rešiti i efikasnije, algoritmom linearne vremenske složenosti.

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

using namespace std;

int p = 31;
long long m = 1e9 + 9;

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

vector<long long> stepeniBrojaP(int n) {
    vector<long long> pStepen(n + 1);

    pStepen[0] = 1;

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

    return pStepen;
}

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

    vector<long long> hesPrefiksa(n + 1);

    hesPrefiksa[0] = 0;

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

    return hesPrefiksa;
}

long long hesSegmenta(const vector<long long>& H,
                      const vector<long long>& P,
                      int i,
                      int j) {
    return (H[j + 1] - (H[i] * P[j + 1 - i]) % m + m) % m;
}

int najduziZajednickiPrefiks(const vector<long long>& H,
                             const vector<long long>& P,
                             int i1,
                             int i2,
                             int n) {
    int l = 0;
    int d = n - 1;

    while (l <= d) {
        int sredina = l + (d - l) / 2;

        if (hesSegmenta(H, P, i1, i1 + sredina) == hesSegmenta(H, P, i2, i2 + sredina)) {
            l = sredina + 1;
        } else {
            d = sredina - 1;
        }
    }

    return l;
}

bool leksikgrafskiManjaNiska(const vector<long long>& H,
                             const vector<long long>& P,
                             int i1,
                             int i2,
                             int n,
                             const string& ss) {
    int k = najduziZajednickiPrefiks(H, P, i1, i2, n);

    return k < n && ss[i1 + k] < ss[i2 + k];
}

string leksikografskiNajmanjaRotacija(const string& s) {
    int n = s.length();

    string ss = s + s;

    vector<long long> H = heseviPrefiksa(ss);
    vector<long long> P = stepeniBrojaP(n);

    int iMin = 0;

    for (int i = 1; i + n < ss.length(); i++) {
        if (leksikgrafskiManjaNiska(H, P, i, iMin, n, ss)) {
            iMin = i;
        }
    }

    return ss.substr(iMin, n);
}

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

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

    return 0;
}