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

U ovom bloku se opisuje glavno rešenje zadatka.

#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;
}