Najduži palindromski segment - Manačerov algoritam

Primer 4.4.1. Za niske ananas, najjaci i list najduži segmenti koji su palindromi su redom anana, ajja i l.

4.4.1 Provera svih segmenata

Problem je moguće rešiti analizom svih segmenata, proverom da li je tekući segment palindrom i određivanjem najdužeg pronađenog palindroma. Pošto je provera da li je niska dužine $n$ palindrom složenosti $O(n)$, a segmenata niske dužine $n$ ukupno ima $O(n^2)$, složenost ovog pristupa je $O(n^3)$.

// provera da li je segment s[i, j] palindrom
bool palindrom(const string &s, int i, int j){
  while (i < j && s[i] == s[j]) {
    i++;
    j--;
  }
  // ako je i < j onda smo nasli s[i] != s[j]
  // te segment nije palindrom, inace jeste
  return i >= j;
}

int main() {
  string s;
  cin >> s;
  int n = s.size();

  int maxDuzina = 0, maxPocetak = 0;
  // za sve moguce segmente date niske
  for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
      // ako je u pitanju palindrom
      if (palindrom(s, i, j)) {
        int duzina = j - i + 1;
        // proveravamo da li je duzi od tekuceg maksimuma
        if (duzina > maxDuzina) {
          maxDuzina = duzina;
          maxPocetak = i;
        }
      }

  // stampamo najduzi palindrom 
  cout << s.substr(maxPocetak, maxDuzina) << endl;  
  return 0;
}

4.4.1 Provera svih segmenata

Implementacija se može malo pojednostaviti i dugački palindromi se mogu pronaći brže, ako se primeti da segmente možemo analizirati redom počev od najdužeg segmenta pa unazad do segmenta dužine 1. Primetimo da će sa ovim redosledom obilaska prvi segment za koji se utvrdi da je palindrom upravo biti najduži palindrom koji tražimo. Ako segmente iste dužine razmatramo u rastućem redosledu indeksa leve granice, u slučaju kada postoji više palindroma iste najveće dužine, kao prvi će biti pronađen onaj koji ima najmanju vrednost indeksa leve granice, kao što je i traženo.

int main() {
  string s;
  cin >> s;
  // duzina niske s
  int n = s.size();
  // potrebno za prekid dvostruke petlje
  bool nasli = false;

  // proveravamo sve duzine d redom, od najvece do najmanje
  // dok ne naidjemo na prvi palindrom
  for (int d = n; d >= 1 && !nasli; d--) {
    // proveravamo rec odredjenu indeksima [p, p + d - 1]
    for (int p = 0; p + d - 1 < n && !nasli; p++) {
      // ako smo naisli na palindrom
      if (palindrom(s, p, p + d - 1)) {
        // ispisujemo ga
        cout << s.substr(p, d) << endl;
        // prekidamo dvostruku petlju
        nasli = true;
      }
    }
  }
  return 0;
}

Primetimo da izlaz iz ugnežđenih petlji nije moguće ostvariti naredbom break (na taj način bi se izašlo iz unutrašnje, ali ne i spoljašnje petlje), već izlaz moramo realizovati pomoću pomoćne logičke promenljive. Složenost najgoreg slučaja ovog pristupa je i ovde $O(n^3)$.

4.4.3 Provera centara

Palindromi poseduju određeno svojstvo inkrementalnosti koje nam može pomoći da pronađemo efikasniji algoritam. Naime, ako je poznat centar palindroma (to može biti bilo neko slovo, bilo pozicija tačno između dva susedna slova) i ako znamo da se $k$ slova oko tog centra slikaju kao u ogledalu i na taj način grade palindrom, onda za proveru da li se $k+1$ slova oko tog centra slikaju kao u ogledalu ne treba proveravati sve iz početka, već je dovoljno samo proveriti da li su dva slova na spoljnim pozicijama ($(k+1)$-vo slovo levo tj. desno od centra) jednaka. Zato efikasnije rešenje dobijamo ako:

Da bismo odredili najduži palindrom sa centrom u slovu $s_i$, širimo palindrom $s_i$ u desno i u levo za $k$ slova dok se nalazimo unutar reči ($i - k \geq 0$ i $i + k < n$) i dok su odgovarajuća slova jednaka ($s_{i-k}=s_{i+k}$). U trenutku kada se to prvi put naruši, pronađen je najduži palindrom sa centrom u slovu $s_i$ (ako se izađe iz reči dalje proširivanje nije moguće, a ako se pronađe različit par slova dalja proširivanja ne mogu više da daju palindrom).

Određivanje najdužeg palindroma sa centrom između slova $s_i$ i $s_{i+1}$ vršimo na analogan način: dok smo unutar reči ($i-k\geq 0$ i $i+k+1<n$) širimo palindrom sve dok važi $s_{i-k}=s_{i+k+1}$.

Za svaku poziciju koja može biti centar palindroma (a njih ima $n$ za slova niske i $n-1$ za pozicije između dva slova niske, tj. ukupno $2n-1$, odnosno $O(n)$) nalazimo najduži palindrom sa centrom u njoj šireći tekući palindrom nalevo i nadesno. Globalno najduži palindrom nalazimo kao najduži od dobijenih palindroma.

Širenje za fiksirani centar palindroma se obavlja u jednom prolasku i zahteva vreme $O(n)$, pa je ukupna složenost ovog algoritma $O(n^2)$.

int main() {
  string s;
  cin >> s;
  // duzina ucitane reci
  int n = s.size();
  // duzina i pocetak najduzeg palindroma
  int maxDuzina = 0, maxPocetak;

  // prolazimo kroz sva slova reci
  for (int i = 0; i < n; i++) {
    int duzina, pocetak;
    
    // nalazenje najduzeg palindroma neparne duzine ciji je centar
    // slovo s[i]
    int k = 1;
    while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
      k++;
    // duzina i pocetak maksimalnog palindroma
    duzina = 2 * k - 1;
    pocetak = i - k + 1;
    // azuriramo maksimum ako je to potrebno
    if (duzina > maxDuzina) {
      maxDuzina = duzina;
      maxPocetak = pocetak;
    }
    
    // nalazenje najduzeg palindroma parne duzine ciji je centar
    // izmedju slova s[i] i s[i+1]
    k = 0;
    while (i - k >= 0 && i + k + 1 < n && s[i - k] == s[i + k + 1])
      k++;
    // duzina i pocetak maksimalnog palindroma
    duzina = 2 * k;
    pocetak = i - k + 1;
    // azuriramo maksimum ako je to potrebno
    if (duzina > maxDuzina) {
      maxDuzina = duzina;
      maxPocetak = pocetak;
    }
  }
  // izdvajamo i ispisujemo odgovarajuci palindrom
  cout << s.substr(maxPocetak, maxDuzina) << endl;  
  return 0;
}

4.4.4 Eksplicitna dopuna reči i pozicija

Postoji nekoliko tehnika koje mogu da uproste implementaciju prethodnog algoritma, objedinjavajući slučajeve palindroma parne i neparne dužine. Zamislimo da se pre prvog, nakon poslednjeg i između svaka dva susedna slova reči postavi specijalni karakter |. Na primer, reč aabcbab dopunjavamo do reči |a|a|b|c|b|a|b|. Na taj način postiže se da su svi centri palindroma karakteri proširene reči i dovoljno je analizirati samo palindrome neparne dužine u proširenoj reči. Ovo dopunjavanje polazne reči je moguće fizički realizovati tako što se u programu eksplicitno kreira dopunjena niska. Ovo uprošćava implementaciju po cenu nešto sporijeg izvršavanja (doduše ne asimptotski) i dodatnog zauzeća memorije.

Napomenimo još i da se i provera pripadnosti indeksa tj. pozicija opsegu reči može eliminisati ako se polazna reč proširi dodatnim specijalnim karakterima na početku i na kraju: ti karakteri moraju biti međusobno različiti i različiti od ostalih karaktera u niski. U tu svrhu mogu da se iskoriste ^ i $, jer se ti karakteri koriste za označavanje početka i kraja u regularnim izrazima.

// da bismo uniformno posmatrali palindrome i parne i neparne duzine,
// prosirujemo nisku dodajuci ^ i $ oko njega i umecuci | izmedju
// svih slova, na primer abc -> ^|a|b|c|$
string dopuni(const string &s) {
  string rez = "^";
  for (int i = 0; i < s.size(); i++)
    rez += "|" + s.substr(i, 1);
  rez += "|$";
  return rez;
}

int main() {
  string s;
  cin >> s;
  string t = dopuni(s);

  // dovoljno je pronaci najveci palindrom neparne duzine u prosirenoj reci
  int maxDuzina = 0, maxCentar;
  // proveravamo sve pozicije u dopunjenoj reci
  for (int i = 1; i < t.size() - 1; i++) {
    // prosirujemo palindrom sa centrom na poziciji i dokle god je to
    // moguce
    int d = 0;
    while (t[i - d - 1] == t[i + d + 1])
      d++;

    // azuriramo maksimum ako je potrebno
    if (d > maxDuzina) { 
      maxDuzina = d;
      maxCentar = i;
    }
  }
  
  // ispisujemo konacan rezultat, odredjujuci pocetak najduzeg palindroma
  int maxPocetak = (maxCentar - maxDuzina) / 2;
  cout << s.substr(maxPocetak, maxDuzina) << endl;
}

4.4.5 Implicitna dopuna reči i pozicija

Da bismo olakšali naredno izlaganje, indekse u dopunjenoj reči (bez dodatih oznaka početka i kraja reči) nazivaćemo pozicije, a u originalnoj reči samo indeksi. Na primer,

Primetimo nekoliko činjenica. Ako je polazna reč dužine $n$, ukupno imamo $N = 2n+1$ pozicija u dopunjenoj reči. Slova polazne reči se nalaze na neparnim pozicijama, dok se na parnim pozicijama nalazi specijalni karakter |. Slovo sa indeksom $k$ se nalazi na poziciji $p = 2k+1$, što znači da se na neparnoj poziciji $p$ nalazi slovo polazne reči sa indeksom $k = \lfloor \frac{p}{2}\rfloor$.

Za svaku poziciju $i$, $0 \leq i < N$, dužinu palindroma sa centrom na toj poziciji možemo odrediti na isti način, bez obzira na to da li je na toj poziciji slovo ili specijalni karakter |. Razmatraćemo dužinu palindroma u polaznoj reči (a ne dopunjenoj) i ona je jednaka broju karaktera sa leve strane date pozicije u dopunjenoj reči koji su jednaki odgovarajućim karakterima sa desne strane te pozicije u dopunjenoj reči. Na primer, u prethodnom primeru za poziciju 7 to je 5, jer je palindrom abcba dužine 5, što odgovara tome da pet karaktera |a|b| sa leve strane karaktera c u dopunjenoj reči odgovaraju karakterima |b|a| sa desne strane karaktera c. Slično važi i za parne pozicije (na primer 2).

Na početku, dužinu palindroma $d$ postavljamo na 1, ako je pozicija $i$ neparna, tj. 0 ako je parna. Zaista, ako je pozicija neparna, na njoj se nalazi slovo polazne reči koje je samo za sebe palindrom dužine 1 (iz drugog ugla gledano, levo i desno od ove pozicije se nalaze karakteri |, pa je bar jedan karakter jednak). Ako je pozicija parna, oko nje se nalaze dva slova (osim u slučaju krajnjih pozicija) i ne znamo unapred da li su ona jednaka, tako da dužinu palindroma inicijalno postavljamo na 0. Na ovaj način postižemo da su brojevi $i - d$ i $i + d$ parni, što znači da su brojevi $i-d-1$ i $i+d+1$ neparni i ako su u opsegu $[0, N)$, oni ukazuju na naredna dva karaktera polazne niske čiju jednakost treba proveriti. Ako su karakteri polazne reči na odgovarajućim indeksima jednaki (to su indeksi $\lfloor \frac{i-d-1}{2}\rfloor$ i $\lfloor \frac{i+d+1}{2}\rfloor$), onda se $d$ uvećava za 2 (iz jednog ugla gledano, ta dva jednaka karaktera se dodaju tekućem palindromu, pa mu se dužina povećava za 2, a iz drugog ugla gledano, ispred prvog i iza drugog se nalaze specijalni znaci | koji su sigurno jednaki i njihovu jednakost nije potrebno eksplicitno proveravati). Na taj način se održava i invarijanta da su brojevi $i + d$ i $i - d$ parni i petlja se može nastaviti na isti način sve dok se ne naiđe na dva različita slova ili se izađe van opsega dopunjene reči.

int main() {
  string s;
  cin >> s;
  // broj pozicija u reci s 
  int N = 2 * s.size() + 1;
  int maxDuzina = 0, maxCentar;
  // za svaki moguci centar palindroma
  for (int i = 0; i < N; i++) {
    // d postavljamo na 0 za parnu, a na 1 za neparnu poziciju
    int d = 0;
    if (i % 2 == 1)
      d = 1;
    
    // dok god su pozicije u opsegu dozvoljenih indeksa i slova
    // na odgovarajucim indeksima jednaka uvecavamo d za 2
    while (i - d - 1 >= 0 && i + d + 1 < N &&
       s[(i - d - 1) / 2] == s[(i + d + 1) / 2])
      // ukljucujemo dva slova u palindrom, pa se duzina uvecava za 2
      d += 2;
    
    if (d > maxDuzina) {
      maxDuzina = d;
      maxCentar = i;
    }
  }
  
  // ispisujemo konacan rezultat, odredjujuci pocetak najduzeg palindroma
  int maxPocetak = (maxCentar - maxDuzina) / 2;
  cout << s.substr(maxPocetak, maxDuzina) << endl;
  return 0;
}

4.4.6 Manačerov algoritam

Primer 4.4.2. Posmatrajmo sada kako izgleda dužina najdužeg palindroma sa centrom u svakoj od pozicija $p$ u reči s = babcbabcbaccba. Obeležimo ovu dužinu sa $d_p$. Obeležimo dopunjenu reč sa $t$. U prvom redu narednog prikaza dati su indeksi $i$ u polaznoj reči $s$, u drugom redu proširena reč $t$, u trećem redu date su pozicije $p$ u proširenoj reči, a u poslednjem vrednost $d_p$.

   0     1     2     3     4     5     6     7     8     9     10    11    12    13    
|  b  |  a  |  b  |  c  |  b  |  a  |  b  |  c  |  b  |  a  |  c  |  c  |  b  |  a  | 
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
0  1  0  3  0  1  0  7  0  1  0  9  0  1  0  5  0  1  0  1  0  1  2  1  0  1  0  1  0

Posmatrajmo, na primer, najduži palindrom sa centrom u poziciji 11 – njegova dužina je $d_{11} = 9$ i on se prostire od pozicije 2 do pozicije 20.

Posmatrajmo sada dužinu najdužeg palindroma sa centrom u poziciji 12. Pošto je prethodno određeni palindrom simetričan oko pozicije 11, poziciji 12, odgovara pozicija 10. Znamo da je $d_{10} = 0$. To je zato što je $t_9 \neq t_{11}$. Međutim, mi znamo da je $t_9 = t_{13}$ (pošto su obe pozicije unutar našeg palindroma), pa je zato $t_{11} \neq t_{13}$ i važi $d_{12}=d_{10}=0$. Primetimo da ovo možemo konstatovati bez ikakve potrebe za novim upoređivanjem karaktera.

Posmatrajmo sada dužinu najdužeg palindroma sa centrom u poziciji 13. Njemu odgovara palindrom sa centrom na poziciji 9. Važi $d_9=1$, jer je $t_8 = t_{10}$ i $t_7 \neq t_{11}$. Na osnovu simetrije palindroma sa centrom u $11$, važi $t_8 = t_{14}$, $t_{10} = t_{12}$, $t_7 = t_{15}$ i $t_{11}=t_{11}$. Zato je $t_{14} = t_{12}$ i $t_{15} \neq t_{11}$, pa je $d_{13} = d_9 = 1$.

Naizgled, važi da je za svako $i$ unutar šireg palindroma sa centrom u nekoj poziciji $C$ broj $d_i$ jednak broju $d_{i'}$, gde se $i'$ određuje kao simetrična pozicija poziciji $i$ u odnosu na poziciju $C$ (važi da je rastojanje od $C$ do $i$ i $i'$ jednako, pa je $C - i' = i - C$, tj. $i' = C - (i - C)$). No, to nije uvek tačno.

Posmatrajmo sada vrednost $d_{15}$ i njoj odgovarajuću vrednost $d_7$. One nisu jednake. Zašto? Posmatrajmo šta je ono što možemo zaključiti iz simetrije palindroma sa centrom na poziciji 11. Važi da je $t_2$ do $t_{12}$ jednako odgovarajućim karakterima $t_{20}$ do $t_{10}$ – to je garantovano simetrijom i nije potrebno proveravati. Međutim, važi $d_7 = 7$. Znamo zato i da je $t_1 = t_{13}$, međutim, ne možemo da tvrdimo da simetrično u odnosu na poziciju 11 važi $t_{21} = t_9$, zato što $t_{21}$ nije više deo palindroma sa centrom na poziciji $C$. Dakle, proveru da li važi $t_{21} = t_9$ je potrebno posebno izvršiti.

Razmotrimo sada opšti slučaj. Pretpostavimo da je $[L, R]$ palindrom sa centrom na poziciji $C$ (tada je $C - L = R - C$), da je $i$ neki indeks unutar tog palindroma (neka je $C < i < R$) i da je $i' = C - (i - C)$ njemu simetričan indeks. Ako je palindrom sa centrom u $i'$ u potpunosti sadržan u palindromu $(L, R)$ (bez uračunatih krajeva), tj. ako je $L < i' - d_{i'}$, tj. $d_{i'} < i' - L = (C - (i - C)) - (C - (R - C)) = R - i$, tada je $d_{i} = d_{i'}$. Dokažimo ovo.

Za svaku vrednost $0 \leq j \leq d_{i'}$ treba dokazati da je $t_{i-j} = t_{i+j}$. Zaista, pošto važi $L < i'-j$ i $i+j < R$, zaključuje se da je $t_{i-j} = t_{i'+j}$ i $t_{i+j} = t_{i'-j}$. Međutim, pošto je $i'$ centar palindroma dužine $d_{i'}$, važi $t_{i'-j} = t_{i'+j}$. Zato se na poziciji $i$ nalazi centar palindroma dužine bar $d_{i'}$. Dokažimo da je ovo i gornje ograničenje, tj. dokažimo da je $t_{i-d_{i'}-1} \neq t_{i+d_{i'}+1}$. Pošto je $i + d_{i'} < R$, važi $i+d_{i'}+1 \leq R$, pa je $t_{i - d_{i'} - 1} = t_{i' + d_{i'} + 1}$ i $t_{i+ d_{i'} + 1} = t_{i'-d_{i'}-1}$. Međutim, pošto je palindrom sa centrom u $i'$ dužine $d_{i'}$, važi $t_{i'-d_{i'}-1} \neq t_{i' + d_{i'} + 1}$.

Ako je $[L, R]$ palindrom sa centrom na poziciji $C$ i ako je $i$ neki indeks unutar tog palindroma ($C < i < R$), ali takav da je $d_{i'} \geq R - i$, onda možemo samo da zaključimo da je $d_{i}\geq R - i$.

Ovo inspiriše naredni algoritam, poznat pod nazivom Manačerov algoritam. Slično kao u prethodnoj verziji algoritma obrađujemo sve pozicije $i$ od $0$ do $N-1$. Pri tom održavamo indekse $C$ i $R$ takve da je $[C - (R - C), R]$ najdesniji do sad pronađeni palindrom. Ako je $i \geq R$, tada palindrom sa centrom u $i$ određujemo iz početka, povećavajući za dva dužinu palindroma $d_i$ koja kreće od 0 ili 1 (u zavisnosti od parnosti pozicije $i$), sve dok je to moguće, isto kao u prethodno opisanom algoritmu. Međutim, ako je $i < R$, tada određujemo vrednost $i' = C - (i - C)$ i ako važi $d_{i'} < R - i$, postavljamo odmah $d_{i} = d_{i'}$. Ako je $d_{i'} \geq R - i$, tada dužinu $d_{i}$ postavljamo na početnu vrednost $R - i$ tj. na $R - i + 1$ tako da su $i - d_i$ i $i + d_{i}$ parni brojevi, i onda je postepeno povećavamo za 2, sve dok je to moguće (opet, veoma slično kao u prethodno opisanom algoritmu). Ako je pronađeni palindrom sa centrom u $i$ takav da mu desni kraj desno od pozicije $R$, onda njega proglašavamo za novi palindrom $[L, R]$, postavljajući mu centar $C = i$ i desni kraj $R = i + d_i$. Na početku možemo inicijalizovati $R = C = 0$ (na taj način obezbeđujemo da ne može da važi $i < R$ i da se na početku neće koristiti simetričnost okružujućeg palindroma).

int main() {
  string s;
  cin >> s;
  // broj pozicija u reci s (pozicije su ili slova originalnih reci,
  // ili su izmedju njih)
  int N = 2 * s.size() + 1;  
  // d[i] je duzina najduzeg palindroma ciji je centar na poziciji i 
  vector<int> d(N);

  // znamo da je [L, R] palindrom sa centrom u C
  int C = 0, R = 0; // L = C - (R - C)
  for (int i = 0; i < N; i++) {
    // karakter simetrican karakteru i u odnosu na centar C
    int i_sim = C - (i - C);
    if (i < R && i + d[i_sim] < R)
      // nalazimo se unutar palindroma [L, R], ciji je centar C
      // palindrom sa centrom u i_sim i palindrom sa centrom u i su
      // celokupno smesteni u palindrom (L, R)
      d[i] = d[i_sim];
    else {
      // ili se ne nalazimo u okviru nekog prethodnog palindroma ili
      // se nalazimo unutar palindroma [L, R], ali je palindrom sa
      // centrom u i_sim takav da nije celokupno smesten u (L, R);
      // u tom slucajmo znamo da je duzina palindroma sa centrom u i bar
      // bar R - i, a da li je vise od toga, treba proveriti
      d[i] = i <= R ? R - i : 0;

      // osiguravamo da je i + d[i] stalno paran broj
      if ((i + d[i]) % 2 == 1)
        d[i]++;

      // dok god su pozicije u dozvoljenom opsegu i slova na odgovarajucim
      // indeksima jednaka uvecavamo d[i] za 2 (jedno slovo s leva i
      // jedno slovo zdesna)
      while (i - d[i] - 1 >= 0 && i + d[i] + 1 < N && 
         s[(i - d[i] - 1) / 2] == s[(i + d[i] + 1) / 2])
        // ukljucujemo dva slova u palindrom, pa se duzina uvecava za 2
        d[i] += 2; 
    }

    // ako palindrom sa centrom u i prosiruje desnu granicu
    // onda njega uzimamo za palindrom [L, R] sa centrom u C
    if (i + d[i] > R) {
      C = i;
      R = i + d[i];
    }
  }

  // pronalazimo najvecu duzinu palindroma i pamtimo njegov centar
  int maxDuzina = 0, maxCentar;
  for (int i = 0; i < N; i++) {
    if (d[i] > maxDuzina) {
      maxDuzina = d[i];
      maxCentar = i;
    }
  }
  
  // ispisujemo konacan rezultat, odredjujuci pocetak najduzeg palindroma
  int maxPocetak = (maxCentar - maxDuzina) / 2;
  cout << s.substr(maxPocetak, maxDuzina) << endl;
  return 0;
}

Složenost ovog algoritma je linearna. Intuitivno, pronalaženje kratkih palindroma zahteva mali broj izvršavanja unutrašnje petlje, dok pronalaženje jednog dugačkog palindroma zahteva duže izvršavanje unutrašnje petlje, ali dovodi do toga da će se u narednim koracima u velikom broju slučajeva u potpunosti izbegavati njeno izvršavanje. Preciznije, svako izvršavanje unutrašnje while petlje povećava vrednost promenljive $R$ (jer je u slučaju else grane $i+d[i]\geq R$, a svako uspešno izvršavanje while petlje uvećava vrednost $d[i]$ za $2$, te će važiti $i+d[i]>R$) koja se nigde ne smanjuje, a čija je maksimalna vrednost $N$, te je ukupan broj izvršavanja unutrašnje petlje ograničen sa $O(N)$.

Možemo razmotriti i varijantu koja eliminiše proveru pripadnosti indeksa opsegu reči na taj način što eksplicitno pravi dopunjenu reč.

string dopuni(const string &s) {
  string rez = "^";
  for (int i = 0; i < s.size(); i++)
    rez += "|" + s.substr(i, 1);
  rez += "|$";
  return rez;
}

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

  // jednostavnosti radi dopunjavamo rec s
  string t = dopuni(s);
  // d[i] je najveci broj takav da je [i - d[i], i + d[i]] palindrom
  // to je ujedno i duzina najduzeg palindroma ciji je centar na
  // poziciji i (pozicije su ili slova originalnih reci, ili su
  // izmedju njih)
  vector<int> d(t.size());
  // znamo da je [L, R] palindrom sa centrom na poziciji C
  int C = 0, R = 0; // L = C - (R - C)
  for (int i = 1; i < t.size() - 1; i++) {
    // karakter simetrican karakteru i u odnosu na centar C
    int i_sim = C - (i - C);
    if (i < R && i + d[i_sim] < R)
      // nalazimo se unutar palindroma [L, R], ciji je centar C
      // palindrom sa centrom u i_sim i palindrom sa centrom u i su
      // celokupno smesteni u palindrom (L, R)
      d[i] = d[i_sim];
    else {
      // ili se ne nalazimo u okviru nekog prethodnog palindroma ili
      // se nalazimo unutar palindroma [L, R], ali je palindrom sa
      // centrom u i_sim takav da nije celokupno smesten u (L, R);
      // u tom slucajmo znamo da je duzina palindroma sa centrom u i bar
      // R - i, a da li je vise od toga, treba proveriti
      d[i] = i <= R ? R-i : 0;
      // prosirujemo palindrom dok god je to moguce krajnji karakteri
      // ^$ obezbedjuju da nije potrebno proveravati granice
      while (t[i - d[i] - 1] == t[i + d[i] + 1])
        d[i]++;
    }

    // ako palindrom sa centrom u i prosiruje desnu granicu
    // onda njega uzimamo za palindrom [L, R] sa centrom u C
    if (i + d[i] > R) {
      C = i;
      R = i + d[i];
    }
  }

  // pronalazimo najvecu duzinu palindroma i pamtimo njegov centar
  int maxDuzina = 0, maxCentar;
  for (int i = 1; i < t.size() - 1; i++)
    if (d[i] > maxDuzina) {
      maxDuzina = d[i];
      maxCentar = i;
    }

  // ispisujemo konacan rezultat, odredjujuci pocetak najduzeg palindroma
  cout << s.substr((maxCentar - maxDuzina) / 2, maxDuzina) << endl;
  return 0;
}

4.4 Najduži palindromski segment - Manačerov algoritam

4.4.1 Provera svih segmenata

4.4.1 Provera svih segmenata

4.4.3 Provera centara

4.4.4 Eksplicitna dopuna reči i pozicija

4.4.5 Implicitna dopuna reči i pozicija

4.4.6 Manačerov algoritam