Why does my rolling hash never work?
hash implementation
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
int A;
int B = ((1LL<<61) - 1);
using namespace std;
void computehash(string &s, vi &h){
int n = s.size();
h[0] = s[0];
for(int i=1;i<n;i++){
h[i] = (h[i-1]*A + s[i])%B;
}
}
void solve(){
string s;
cin >> s;
int n = s.size();
vi h(n);
computehash(s, h);
vi pow(n);
pow[0] = 1;
for(int i=1;i<n;i++){
pow[i] = (pow[i-1]*A)%B;
}
for(int l=n-1;l>1;l--){
int a = l-1;
int b = n-l;
if(a<b) break;
cout << "\n";
int hash1 = h[a];
int hash2 = (h[n-1] - h[b-1]*pow[n-b])%B;
if(hash1 == hash2){
cout << "YES\n";
cout << s.substr(1,l);
return;
}
}
cout << "NO\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1,B-1);
A = dist(rng);
solve();
return 0;
}
Because of an integer overflow. The values for $$$h[i]$$$ can reach up to $$$B-1$$$, and multiplying that with $$$A$$$ likely causes an integer overflow.
whats the solution to this?
use long long
what's happening is that the value is getting too big to be stored into "int" before you take the mod hence the problem
i have int macroed to long long tho
Oh okay.
now suppose some index k, h[k]=(1ll<<61)-2, now suppose A=1e9, now h[k]*A would overflow long long. Do not keep the mod values so big. try to keep it upto 1e9+7 in general to avoid overflows.
is that ok given the birthday paradox, is it still safe?
I lowered B to 1e9+7 and unless A is very small, <10, it still fails.
int hash2 = (h[n-1] — h[b-1]*pow[n-b])%B; this line might also lead to incorrect results as the quantity inside the brackets might be -ve and result might not be as expected, try something like: int hash2 = (h[n-1] — (h[b-1]*pow[n-b])%B+B)%B; given you handled other overflows correctly.
what fixed it was "if(hash2<0){ hash2+=B; }" though I dont understand why because the prefix hash should be less than the original right??????
You are taking the mod at every step. Any such inequalities are not maintained after that.