题目：http://ybt.ssoier.cn:8088/problem_show.php?pid=1455

题目描述：在母串里找子串出现的次数

题目思路：与字符串的搜索有关那就立刻找到哈希

从s[1]到s[m]将从第1位到第i位的哈希值算出来

在以m-n为固定的差值定义字串长度，在找到每一个子串

属于哈希模板题

#include<bits/stdc++.h>
using namespace std;
const int b=31;//我们需要一个质数
#define N 1000001
#define ull unsigned long long
//需要一个超级大的存储，否则数字太大，如果溢出过多就会很麻烦
ull p[N],sum[N],x;
int t,ans,i,n,m;
char s1[N],s2[N];
int main(){
    p[0]=1;//（b^0=1）
    for(i=1;i<=N;++i){
        p[i]=p[i-1]*b;//先把这些次方都存起来，以后有用
    }
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%s%s",s1+1,s2+1);
        //s1是我们要找的子串
         //s2是母串
        n=strlen(s1+1);//长度
        m=strlen(s2+1);//长度
        sum[0]=0;//先初始化防止后面根据公式计算哈希值的时候有多余的东西
        for(i=1;i<=m;++i){
            sum[i]=sum[i-1]*b+(ull)(s2[i]-'A'+1);
        }//声明：公式H[m]=（C[1]*b^(m-1)+C[2]*b^(m-2)+...+C[m]*1）
        x=0;//同样的道理
        for(i=1;i<=n;++i){
            x=x*b+(ull)(s1[i]-'A'+1);
        }
        for(i=0;i<=m-n;++i){
            if(x==sum[i+n]-sum[i]*p[n]){
            //如果分段上的哈希值对上了
            //注：以第一个数字为将要搜索的子串的起点，一直轮班到第m-n个，可以找遍所有子串
            //(sum[i+n]-sum[i]*p[n])是计算子串哈希的公式,可以做一个H[m]和H[n]自行推导（m<n)
                ans++;//搜索数量加1
            }
        }
        printf("%d\n",ans);//输出
    }
    return 0;
}

题目总结：做好哈希一类的题我们需要考虑三个方面

一：对公式的推导

首先是基本公式 H[m]=（C[1]*b^(m-1)+C[2]*b^(m-2)+…+C[m]*1）

然后就是对子串的计算

对于C'=C[1]C[2]…C[n]

H[C']=H[k+n]-H[k]*b^n

二：对b^n的优化

直接在前面就存是最好的选择

三：比较

哈希值相同的字符串大概率相同，在一些题目中可以近似为一定相同

哈希值不同的字符串一定不同