哈希

哈希的思想比较简单，其实就是把一个字符串看做一个高进制的数。

滚动哈希

子字符串匹配，复杂度O(n+m)。

-流程

我盟选取两个合适的互质的常数b和h(b<h)，假设字符串为C=$C_1C_2C_3..C_n$那么我们定义哈希函数H(C)=($C_1b^{m-1}+C_2b^{m-2}…+C_mb^0$)mod h

-递推计算

H(C,k)为前k个字符构成的字符串的哈希值，则:(以下不考虑取模)则： \(H(C,K+1)=H(C,k)*b+C_{k+1}\) 递推处理完主字符串(你明白什么意思)的哈希，然后以下是O(1)求子串的哈希 \(H(C')=H(C,k+n)-H(C,k)*b^n\) 这样的时间复杂度是O(m+n);

哈希的正确性

可以使用双哈希来大大降低哈希冲突(两个不同字符串的hash值相等)

附：一些质数

3255433 3255437 3255451 3255467 3255491 3255493 3255529 3255547 3255557 3255559 3255583 3255587 3255601