Hash.cpp

const int P = max(rand(), 239017) | 1;
const int N = 500020;

const int MOD1 = 1000000007;
const int MOD2 = 1000000009;

array<pair<int, int>, N> p;

bool initp()
{
	p[0].F = p[0].S = 1;
	for (int i = 1; i < N; i++)
	{
		p[i].F = (p[i-1].F * 1ll * P) % MOD1;
		p[i].S = (p[i-1].S * 1ll * P) % MOD2;
	}
}

bool __init = initp();


struct Hash 
{
	vector<pair<int, int > > h; 
	int n;
	
	pair<int, int> operator()(int l, int r)
	{
		int len = r - l + 1;
		int h1 = h[r].F;
		if (l) h1 -= 1ll * h[l - 1].F * p[len].F % MOD1;
		h1 %= MOD1;
		if (h1 < 0) h1 += MOD1;
	   
		int h2 = h[r].S;
		if (l) h2 -= 1ll * h[l - 1].S * p[len].S % MOD2;
		h2 %= MOD2;
		if (h2 < 0) h2 += MOD2;
		return {h1, h2};
	}
	
	Hash(const string& s) : h(s.size()), n(s.size())
	{
		h[0] = mkp(s[0], s[0]);
		
		for(int i = 1; i < s.size(); i++)
		{
			h[i].F = (h[i-1].F * 1ll * P) % MOD1;
			h[i].F = (h[i].F * 1ll + s[i]) % MOD1;
			
			h[i].S = (h[i-1].S * 1ll * P) % MOD2;
			h[i].S = (h[i].S * 1ll + s[i]) % MOD2;
		}
	}
};

string sbt(string& s, int l, int r)
{
	assert(l >= 0 && r < s.size());
	string ar;
	
	for(int i = l; i <= r; i++)
		ar += s[i];
	
	return ar;
}