hash

int hash(ll x)
{
	ll t = x % N;
	while (h[t] && h[t] != x) t = (t + 1) % N;
	return t;
}

int main()
{
	fo(i, 1, n)
		x = (x * 26 + s[i] - 97) % mo;
	t = hash(x);
	h[t] = x;
}

double hash

int hash(ll x, ll y)
{
	ll t = x % N;
	while (h[t][0] && (h[t][0] != x || h[t][1] != y)) t = (t + 1) % N;
	return t;
}

int main()
{
	fo(i, 1, n)
	{
		x = (x * 26 + s[i] - 97) % mo;
		y = (y * 26 + s[i] - 97) % mo1;
	}
	t = hash(x, y);
	h[t][0] = x, h[t][1] = y;
}

hash字符串中的子串

int main()
{
	cf[0] = 1;
	fo(i, 1, n) cf[i] = cf[i - 1]  * 26; 
	fo(i, 1, n)
		qz[i] = (qz[i - 1] * 26 + s[i] - 97) % mo;
//	对于[i~j]的hash值 
	(qz[j] - qz[i - 1] * cf[j - i + 1] % mo + mo) % mo;
}

树hash

树(hash)用来比较树是否同构。

详见该博客

转载需注明出处。