Opis glavnog rešenja

Naivno rešenje bi moglo da sadrži funkciju koja proverava da li je niska palindrom. Ako je niska odmah palindrom, nema potrebe bilo šta dalje proveravati i ne treba dodati nijedan karakter. Ukoliko niska nije palindrom, možemo iz nje izbaciti poslednji karakter i onda proveriti da li je novodobijena niska palindrom. Postupak ponavljamo sve dok ne dođemo do toga da je niska postala palindrom ili da je postala prazna. Broj karaktera koje smo izbacili predstavlja upravo broj karaktera koje treba dodati u obrnutom redosledu na početka niske kako bi ona postala palindrom. S obzirom da svaki put kada izbacimo karakter proveravamo da li je niska palindrom, što se može uraditi u lineranom vremenu, ukupna složenost algoritma je \(O(n^2)\).

Bolje rešenje zahteva upotrebu KMP algoritma. Prvo ćemo uzeti originalnu nisku i na nju dodati specijalni karakter. Specijalni karakter može biti bilo koji karakter koji se ne javlja u niski. Neka to bude $$. Nakon toga na tako dobijenu nisku nalepimo obrnutu originalnu nisku. Na primer, neka je početna niska bila \(aaba\). Opisanim postupkom dobijamo nisku \(aaba\$abaa\). Zatim računamo prefiksnu tabelu iz KMP algoritma. Na ovaj način za svaku poziciju dobijamo najduži sufiks koji je ujedno i prefiks niske. Ono što nas zanima je samo poslednji zapis u tabeli, odnosno najduži sufiks koji je ujedno i prefiks i završava se na kraju novoformirane niske. Kada dobijemo taj podatak, potrebno je uzeti sve karaktere niske \(S[1..n]\) nakon izračunatog sufiksa, obrnuti ih i na njih nalepiti početnu nisku. U našem primeru, na poslednjoj poziciji u sufiksnom nizu se nalazi 2, odnosno najduži sufiks koji je i prefiks je podniska \(aa\). Uzimanjem podniske \(S[1+2..n]\) niske \(S[1..n]\), obrtanjem iste i nalepljivanjem originalne niske dobijamo \(abaaba\) i time dobijamo dopunu do palindroma. U ovom pristupu samo računamo prefiksnu tabelu nad niskom dužine \(2n + 1\) pa je vremenska složenost algoritma \(O(n)\).

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

using namespace std;

void compute_prefix_table(string &pattern, vector<int> &prefix_table)
{
    int n = pattern.size();

    prefix_table[0] = 0;

    // Indeks i je indeks koji ide kroz nisku, a indeks j ce zapravo 
    // sluziti da kaze kolika je duzina prefiksa i sufiksa koji se poklapaju.
    int i = 1, j = 0;

    while (i < n) {
        // Ukoliko poklopimo odgovarajuca 2 karaktera, potrebno je da na 
        // poziciju i smestimo j + 1 sto nam zapravo kaze kolika je duzina 
        // sufiksa niske pattern[0-i] koji se poklapa sa prefiksom reci, tj. 
        // kaze nam od koje pozicije u niski text nastavljamo pretragu ako 
        // nema poklapanja teksta i uzorka na nekoj poziciji. Ako smo nasli 
        // poklapanje uvecavamo oba indeksa.
        if (pattern[i] == pattern[j]) {
            prefix_table[i] = j + 1;
            i++;
            j++;
        }
        else {
            if (j != 0) {
                j = prefix_table[j - 1];
            }
            else {
                prefix_table[i] = 0;
                i++;
            }
        }
    }
}

string change_string(const string &s)
{
    string tmp_1 = s;
    reverse(tmp_1.begin(), tmp_1.end());

    string tmp = s + "#" + tmp_1;

    int n = tmp.size();
    vector<int> prefix_table(n);
    compute_prefix_table(tmp, prefix_table);

    string suffix = s.substr(prefix_table[n - 1]);
    reverse(suffix.begin(), suffix.end());
    suffix += s;

    return suffix;
}

int main ()
{
    string s = "aacaaa";

    cout << change_string(s) << endl;

    return 0;
}