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