Hash
把一个字符串映射成一个整数，可以方便的比较两个字符串是否相等，
计算 \(Hash\) 值:
\[\displaystyle \sum_{i=0}^{len-1}(s[i] \times B^{len-1-i})(mod\;M) \]这里的 \(B\) 是任取的一个大小合适的数，\(M\) 就是为了把算出来的值映射到 \([0,M-1]\) 的范围内，
既然是 \(mod\) ，就会有重复的值，也就是 “Hash碰撞”（“Hash冲突”），两个不相同的字符串映射到了同一个值上。
“Hash碰撞”不可避免，只要知道模数 \(M\) 就一定可以卡，一般 \(M\) 我们取一个较大的质数，
不常用的最好（防止常用的被卡），更方便的可以用 \(unsigned \;long \;long\) 的自然溢出，
最保险的是取双模数，即每个串 Hash 两个值，分别比较。
例题
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int M = 99995699,B = 233;
typedef unsigned long long ULL;
int t,n,m;
string a,b;
ULL hs[1000005],p[1000005];
ULL gh(int l,int r)
{
return (hs[r]-hs[l-1]*p[r-l+1]);
}
int main()
{
scanf("%d",&t);
while(t--)
{
long long ans=0;
cin>>a>>b;
n=a.length(), m=b.length();
p[0]=1;
ULL tmp=0;
for(int i=0;i<n;i++) tmp=tmp*B+a[i];
for(int i=0;i<m;i++)
{
hs[i+1]=hs[i]*B+b[i];
p[i+1]=p[i]*B;
}
for(int i=1,j=n;j<=m;j++,i++)
if(gh(i,j)==tmp) ans++;
printf("%d\n",ans);
}
return 0;
}
注意
字符串从 \(0\) 开始，
hs数组下标从 \(1\) 开始！！！（唐）
标签：Hash,trie,hs,long,int,ULL,KMP,字符串 From： https://www.cnblogs.com/ppllxx/p/18155009