Opis glavnog rešenja

Naivno rešenje je da redom probamo sve moguće vrednosti parametra \(k\). Za svako \(k\) od 0 do 25 napravimo novu nisku tako što svako slovo imena grada rotiramo za \(k\) mesta udesno kroz engleski alfabet. Zatim proverimo da li se tako dobijena niska pojavljuje kao podniska presretnute poruke. Ako se pojavljuje, vrednost \(k\) ispisujemo. Ovo rešenje je jednostavno, ali za svaku vrednost \(k\) ponovo formira rotiranu reč i ponovo traži njeno pojavljivanje u tekstu.

Pametnije rešenje koristi osobinu da ciklična rotacija čuva razlike između susednih slova. Na primer, ako se svako slovo neke reči pomeri za isti broj mesta, razlika između prvog i drugog slova, drugog i trećeg, i tako dalje, ostaje ista modulo 26. Zato umesto da poredimo sve moguće rotacije cele reči, možemo porediti nizove razlika susednih slova.

Od imena grada \(s\) pravimo nisku \(ds\) u kojoj je svaki karakter jednak razlici dva susedna slova u \(s\), računatoj modulo 26. Isto radimo i za tekst poruke \(t\), čime dobijamo nisku \(dt\). Ako se \(ds\) pojavljuje u \(dt\) na nekoj poziciji, to znači da deo poruke koji počinje na toj poziciji ima isti oblik kao ime grada, samo su sva njegova slova rotirana za isti broj mesta. Tada vrednost \(k\) možemo odrediti poređenjem prvog slova tog dela poruke i prvog slova imena grada.

Za efikasno traženje svih pojavljivanja koristi se Z-algoritam. Formira se niska oblika \(ds + \$ + dt\), gde je znak \(\$\) separator koji se ne pojavljuje u šifrovanom alfabetu. Z-vrednost na pozicijama koje pripadaju delu \(dt\) govori koliko se karaktera odatle poklapa sa početkom niske, tj. sa \(ds\). Kada je ta vrednost bar \(|ds|\), pronađeno je pojavljivanje oblika imena grada u tekstu, pa se iz prve odgovarajuće pozicije računa kandidat za \(k\).

Poseban slučaj nastaje kada ime grada ima dužinu 1. Tada nema susednih slova, pa nema ni niza razlika koji bismo mogli da uporedimo. U tom slučaju svako slovo poruke može predstavljati rotirano jedino slovo imena grada, pa se za svako slovo poruke direktno računa odgovarajuća vrednost \(k\).

Naivno rešenje proverava 26 rotacija i za svaku traži pojavljivanje u poruci. Implementirano rešenje pravi nizove razlika i jednom primenjuje Z-algoritam, pa radi u linearnoj složenosti \(O(|s| + |t|)\). Memorijska složenost je takođe \(O(|s| + |t|)\) zbog pomoćnih niski i Z-niza.

#include<iostream>
#include<vector>

using namespace std;

vector<int> calculate_z_array(const string &s) {
   int n = s.size();
   vector<int> z(n);
   int l = 0;
   int r = 0;

   for (int i = 1; i < n; i++) {
      if (i <= r) {
         z[i] = min(r - i + 1, z[i - l]);
      }

      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
         z[i]++;
      }

      if (i + z[i] - 1 > r) {
         l = i;
         r = i + z[i] - 1;
      }
   }

   return z;
}


int main(){

   string s, t;

   cin >> s >> t;

   vector<bool> possible(26, false);

   if(s.length() == 1){
      for(char c : t){
         int k = (c - s[0] + 26) % 26;
         possible[k] = true;
      }
   } else if(s.length() <= t.length()){
      string ds, dt;

      for(size_t i = 1; i < s.length(); i++){
         int d = (s[i] - s[i - 1] + 26) % 26;
         ds.push_back('a' + d);
      }

      for(size_t i = 1; i < t.length(); i++){
         int d = (t[i] - t[i - 1] + 26) % 26;
         dt.push_back('a' + d);
      }

      string combined = ds + "$" + dt;
      vector<int> z_array = calculate_z_array(combined);

      for(size_t i = ds.length() + 1; i < combined.length(); i++){
         if(z_array[i] >= (int)ds.length()){
            size_t position = i - ds.length() - 1;
            int k = (t[position] - s[0] + 26) % 26;
            possible[k] = true;
         }
      }
   }

   for(int i = 0; i < 26; i++){
      if(possible[i])
         cout << i << endl;
   }

   return 0;
}