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) 
{
    const 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;

    auto text = s + "#" + t + t.substr(0, t.size() - 1);
    auto z_array = calculate_z_array(text);

    int counter = 0;

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

    cout << counter << endl;

    return 0;
}