rolling_hash.cpp

long long compute_hash(string s) {
	const int p = 31; //prime number 
	const int m = 1e9 + 9;
	long long hash_value = 0;
	long long p_pow = 1;
	for(char c : s) {
	hash_value = (hash_value + (c - 'a' + 1) * p_pow)  % m;
	p_pow = (p_pow * p) % m;

	}
	return hash_value;
}


long long rolling_hash(string prev , char nxt) 
{
	const int p = 31;
	const int m  = 1e9 + 9;
	long long H = compute_hash(prev)
	long long Hnxt = ((H - pow(prev[0] , prev.length() - 1)) * p + (int)nxt) % m;
	return Hnxt;

}