String_hashing_pattern_matching

// Problem: E. Check Transcription

// Contest: Codeforces - Mail.Ru Cup 2018 Round 3

// URL: https://codeforces.com/problemset/problem/1056/E

// Memory Limit: 256 MB

// Time Limit: 3000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

using ld = long double;

//using li = __int128_t ; g++ compiler provides 128bit - (-2^127 to 2^127-1)

#define pb emplace_back

#define mp make_pair

#define mt make_tuple

#define lwb lower_bound

#define upb upper_bound

#define F first

#define S second

#define I insert

#define P pair<ll, ll>

#define graph unordered_map<ll ,vector<ll>>

#define all(x) x.begin(), x.end()

#define repv(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define rep(i, a, b) for(int i = a; i < b; i++)

#define printv(v) for(auto x : v) cout << x << " ";

#define printa(a, n) for(int i = 0; i < n; i++) cout << a[i] << " ";

#define scana(a, n) for(int i = 0; i < n; i++) cin >> a[i];

#define init1(a, x, n) for(int i = 0; i < n; i++) a[i] = x;

#define init2(a, x, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = x;

#define bits(n) __builtin_popcountll(n)

#define setpr(n) fixed << setprecision(n)

#define gcd(a, b) __gcd(a, b)

#define nextPermut(x) next_permutation(x.begin(), x.end())

#define nl "\n"

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define printOK cout << "👍\n" ;

const ll mod = 1000000007, maxn = 2e5 + 5;

inline ll add(ll a, ll b, ll m) { return (((a % m) + (b % m)) % m); }

inline ll mul(ll a, ll b, ll m) { return (((a % m) * (b % m)) % m); }

inline ll sub(ll a, ll b, ll m) { return (((a % m) - (b % m) + m) % m); }

using namespace std ;

const ll M = 1e9 + 9 , p = 9973 , MS = 1000001;

ll H[MS];

ll Pow[MS] ;

ll n, N;

void gen_hash(string t ){

H[0] = 1;

for(ll i = 1 ; i <=N ; i++){

H[i] = ((H[i-1]*p)%M + t[i-1])%M ;

}

}

void gen_pow(){

Pow[0] =1 ;

for(ll i = 1 ; i < MS ; i++){

Pow[i] = (Pow[i-1]*p)%M ;

}

}

ll getHash(int a , int b ){

return (H[b+1] - (H[a]*Pow[b-a+1])%M + M )%M ;

}

ll Count(string s , char chr ){

ll retVal = 0 ;

for(auto &c : s ){

if(c == chr)retVal++;

}

return retVal ;

}

int main(){

FIO

string s , t ;

cin >> s >> t ;

n = s.size();

N = t.size();

gen_hash(t) ;

gen_pow() ;

ll count0 = Count(s, '0'), count1 = Count(s,'1');

set<pair<int,int>> satLens ;

for(int i = 1 ; i < N ;i++){//0

int req = N-(count0)*i ;

if(req > 0 && req%count1 == 0)

satLens.insert({i,req/count1});

}

for(int i = 1 ; i < N ; i++){//1

ll req =N-(count1*i) ;

if (req > 0 && req%count0 == 0 )

satLens.insert({req/count0,i}) ;

}

// I have the pairs that satisfy the length

ll retVal = 0 ;

for(auto &c : satLens){

ll r0 = -1 , r1 = -1 ;

bool got = true ;

ll j = 0 , i = 0 ;

for(i = 0 ;i < n && j < N ; i++){

if(s[i] == '0'){

if(r0 != -1){

if(j+c.first > N || r0 != getHash(j,j+c.first-1)){

got = false ;

break ;

}

}else r0 = getHash(j,j+c.first-1) ;

j = j+c.first ;

}else{

if(r1 != -1){

if(j+c.second > N ||r1 != getHash(j,j+c.second-1)){got = false ;break ; }

}else r1 =getHash(j,j+c.second-1);

j = j+c.second ;

}

}

if(got && r0 != r1 )retVal++ ;

}

cout << retVal << "\n" ;

return 0 ;

}