String Hashing (Gold) - CF - Check Transcriptions

Debugging Help
#1

CF - Check Transcription

Here is my code that doesn’t work.

#include <bits/stdc++.h>
using namespace std;

string s, t;

typedef long long ll;
ll base = 31;
ll MOD = 1e9+7;

ll inv;

ll po[1000100];
ll invpo[1000100];
ll chash[1000100];

ll chashing(int l, int r){
    if (l == 0){
        return chash[r];
    }
    return (chash[r]-chash[l-1]+MOD)*invpo[l]%MOD;
}

long long binpow(int base, int power, int mod){
    if (power < 0) return 0;
    long long ret = 1;
    long long mult = base;
    while (power > 0){
        if (power%2 == 1){
            ret *= mult;
            ret %= mod;
        }
        mult *= mult;
        mult %= mod;
        power /= 2;
    }
    return ret;
}

int main(){
    inv = binpow(base, MOD-2, MOD);
    po[0] = 1;
    invpo[0] = 1;
    for (int i = 1; i <= 1e6; i++){
        po[i] = po[i-1]*base%MOD;
        invpo[i] = invpo[i-1]*inv%MOD;
    }
    cin >> s >> t;
    chash[0] = t[0]-'a'+1;
    for (int i = 1; i < (int)t.size(); i++){
        chash[i] = chash[i-1]*base+t[i]-'a'+1;
        chash[i] %= MOD;
    }
    int zero = 0, one = 0;
    for (int i = 0; i < (int)s.size(); i++){
        if (s[i] == '0')
            zero++;
        else
            one++;
    }
    if (s[0] == '1'){
        swap(zero, one);
        for (int i = 0; i < (int)s.size(); i++){
            if (s[i] == '0')
                s[i] = '1';
            else
                s[i] = '0';
        }
    }
    int ans = 0;
    for (int i = 0; i*zero < (int)t.size(); i++){
        int onelen = ((int)t.size()-(i+1)*zero)/one;
        if (onelen == 0 || onelen*one != (int)t.size()-(i+1)*zero)
            continue;
        vector<ll> a, b;
        int cur = 0;
        for (int j = 0; j < (int)s.size(); j++){
            if (s[j] == '0'){
                a.push_back(chashing(cur, cur+i));
                cur += i+1;
            } else {
                b.push_back(chashing(cur, cur+onelen-1));
                cur += onelen;
            }
        }
        bool work = true;
        for (auto x : a) if (x != a[0]) work = false;
        for (auto x : b) if (x != b[0]) work = false;
        if (work && a[0] != b[0])
            ans++;
    }
    cout << ans << "\n";
}

I figured out where my code is wrong: If I change the “chashing” function to

ll chashing(int l, int r){
    if (l == 0){
        return chash[r];
    }
    return (chash[r]-chash[l-1]*po[r-l+1]%MOD+MOD)%MOD;
}

Then it works. Both appear to be valid hashing functions, but why does my original code not work?

#2

Figured it out, my hash only works if hash[i] = \Sigma_{k=0}^is[k]*base^k while I’m defining hash[i] = \Sigma_{k=0}^is[k]*base^{i-k}