Nula XOR

Neka su date dve binarne niske \(S\) i \(T\). Prebrojati koliko postoji cikličnih permutacija niske \(T\) takvih da sa niskom \(S\) primenom operacije XOR daju rezultat 0.

Opis ulaza

Sa standardnog ulaza se unose 2 niske \(S\) i \(T\).

Opis izlaza

Na standardni izlaz ispisati broj cikličnih permutacija koje zadovoljavaju navedeni uslov.

Primer

Ulaz

101
101

Izlaz

1

Rešenje

Opis glavnog rešenja

Zadatak se svodi na rešavanje sledećeg problema: koliko rotacija jedne niske izgleda isto kao druga niska?

Umesto da posebno pravimo svaku rotaciju, koristimo sledeću ideju: ako nisku zalepimo samu na sebe (bez poslednjeg karaktera), sve njene rotacije se pojavljuju kao delovi te nove niske. Rotacije početne reči možemo pronaći tako što gledamo prozore odgovarajuće dužine kroz tu “dupliranu” reč. Na primer, za reč abc, “duplirana” niska bi bila abcab, a njene podniske abc, bca i cab su rotacije polazne reči.

Pošto ne želimo da pretražujemo naivno karakter po karakter za svaku rotaciju, koristi se Z-algoritam za pretraživanje niske.

#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++) {
      // Ako je tekuca pozicija unutar opsega [l,r] koristimo prethodno izracunatu vrednost za inicijalizaciju
      if (i <= r) {
         z[i] = min(r - i + 1, z[i - l]);
      }

      // Preskacemo proveru karaktera od pozicije i do pozicije z[i].
      // Poredimo karakter po karakter u niski i sve dok se karakteri poklapaju povecavamo vrednost z[i]
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
         z[i]++;
      }

      // Ako je nova vrednost desnog kraja intervala poklapanja veca od prethodne vrednosti, azuriramo interval [l,r]
      if (i + z[i] - 1 > r) {
         l = i;
         r = i + z[i] - 1;
      }
   }

   return z;
}

int main(){

   string s, t;

   cin >> s >> t;

   string t1 = t + t.substr(0, t.size() - 1);

   string s1 = s + "#" + t1;

   vector<int> z_array = calculate_z_array(s1);

   int counter = 0;

   for (int x : z_array) {
      if (x == s.size()) {
         counter++;
      }
   }

   std::cout << counter << "\n";

   return 0;
}