字符串哈希

方法

通常采用多项式 Hash 的方法，也就是说将字符串看做一个 b 进制的数。

进制数选择（大于所有字符对应的数字的最大值，且为质数），如：131 233 13331 19260817 等。

模数选择（双\(10^9\)的模数或者直接自然溢出）：19260817 19660813 等。

然后就可以愉快的哈希了！

ull hashh (string s) {
	ull res = 0;
	for (int i = s.size () - 1; i >= 0; i --) {
		res = (base * res + (s[i] - 'a'));
	}
	return res;
}

子串哈希

如何得到子串的哈希值呢？

可以先对字符串的每个前缀进行预处理，根据哈希方法：

定义字符串前缀的哈希值为 \(p_i=s_1×b^{i-1}+s_2×b^{i-2}+…+s_i\)，

那么子串 \(s_{l-r}\) 的哈希值就为 \(p_{l-r}=p_{r}-p_{l-1}×b^{r-l+1}\) 。

这里的 \(b^{r-l+1}\) 可以通过预处理然后 \(O(1)\) 查询，也可以直接快速幂
\(O(\log n)\) 搞定。

void hashh (string s) {
	h[0] = s[0] - 'a' + 1;
	for (int i = 1; i < s.size(); i ++) {
		h[i] = h[i - 1] * base + s[i] - 'a' + 1;
	}
}

cin >> l >> r;
cout << h[r] - h[l - 1] * qpow (base, r - l + 1);

可以应用到字符串匹配。