Polynomial Hashing Algorithm for Strings

hash.cpp

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int maxn = 100100;

// prime bigger than any value of the original string
const ull p = 113;

ull p_pow1[maxn];

ull ha[maxn];
ull hb[maxn];

string a;
string b;

// calculate all powers of p up to n
void init(ull *p_pow, ull mod)
{
	p_pow[0] = 1;
	for (int i = 1; i < maxn; i++) p_pow[i] = (p_pow[i-1]*p)%mod;
}

// hash string
// hash[i] = ( x[0] + x[1]*(p^1) + .. + x[i]*(p^i) ) mod 2^64
void hasha(string &a, ull *hx, ull mod, ull *p_pow)
{
	hx[0] = a[0]-'0'+1;

	for (int i = 1; i < a.size(); i++) {

		hx[i] = (a[i]-'0'+1)*p_pow[i];
		hx[i] += hx[i-1];
		hx[i] %= mod;
	}
}

int main()
{
	cin >> a;
	cin >> b;

	ull mod1 = 1000000007;
	
	init(p_pow1, mod1);
	
	hasha(a, ha, mod1, p_pow1);
	hasha(b, hb, mod1, p_pow1);

	return 0;
}