1056E - Check Transcription - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000001 
const long long M = 1e9+9;//
const long long B = 69421;
/*
abcd
a = > a
ab = > a*B+b
abc => a*B^2+b^1+c
abcd =>a*B^3 +b*B^2 +c*B^1 +d
so , cd c*B+d <=>  abcd - ab => (a*B^3 +b*B^2 +c*B^1 +d) - (a*B+b)*B^2
so, if pre[1] is a's hash, cd is l to r(2 to 3) is pre[4]- pre[2]*B^(4-3+1) is pre[r+1]-pre[l]*B^(r-l+1)   
*/

long long pows[maxn];
long long pre[maxn];
long long m,n;
string s,t;
 	
long long gethash( int l, int r)
{
	long long num = pre[r+1] - pre[l] * pows[r-l+1]%M;
	if (num < 0) return num+M;
	return num;  
}

bool rok(int r0len,int r1len) 
{
//	cout << r0len << " " << r1len << endl;
	int i = 0; //position in t 
	long long r0num = -1, r1num =-1;
	for (auto c : s) 
	{
		if (c == '0') {
			if (r0num == -1) 
				r0num = gethash(i,i+r0len-1);
			else {
				if (r0num != gethash(i,i+r0len-1)) return false;
			}
			i += r0len;
		}
		else{
			if (r1num == -1) 
				r1num = gethash(i,i+r1len-1);

			else {
				if (r1num != gethash(i,i+r1len-1)) return false;
			}
			i += r1len;
		}
		//if (i >= n) return false;
	}
	if (r0num == r1num) return false;
	return true;
}
int main() {
 	ios::sync_with_stdio(0);
	cin.tie(0);	
	cout.tie(0);
 //	freopen("censor.in","r",stdin);
 //	freopen("censor.out","w",stdout);
  

 	cin >> s >> t;
    m = s.length(); 
 	n = t.size();
	

 	pows[0] = 1;
 	for (int i =1 ; i <= n; i++) pows[i] = pows[i-1]*B % M;
 
 	pre[0] = 0;
 	
 	for (int i = 0; i < n; i++) 
	 	pre[i+1]  = (pre[i]*B%M+t[i]) % M;
	 	
	long long ans = 0;
  	
  	long long zerocnt = 0,onecnt; 
 	for (auto c: s) if (c == '0') zerocnt++;
	onecnt = m - zerocnt;
	
	for (long long r0len = 1; r0len < n; r0len++) 
	{
		//r0len is possible r0 length
		if ((n - r0len* zerocnt)% onecnt != 0 ) continue;
		long long r1len = (n - r0len* zerocnt) / onecnt;
		if (r1len <= 0) continue;
		if (rok(r0len,r1len)) ans++;	
	}	
	 
	cout << ans << '\n';
   
  	return 0;
}