2023年7月20日发(作者：)

DaimayuanOnlineJudge⼩蜗的疑问现在给你两个字符串aa和bb，aa和bb都由⼩写字母构成。⼩蜗想知道字符串bb在aa中出现了⼏次(出现位置可以重叠)。输⼊格式第⼀⾏两个整数n,mn,m，分别表⽰aa和bb的长度。接下来两⾏，给出字符串aa和bb。输出格式输出⼀个数，表⽰答案。样例输⼊7 2aaaabaaaa样例输出4数据规模对于100%100%的数据，保证1≤n,m≤2000001≤n,m≤200000。思路：这个题与⼗分相似，但是那个题只是需要字符出现即可，并没有指定⼦串为特定值，所以那个题⽤区间的前缀和与⼆分就⾏，但这个题是⼦串与主串的对⽐，是KMP，但是我们可以⽤哈希完全代替KMP，KMP能做的哈希都能做，并且哈希⽤处更全更简单，所以与KMP有关的直接⽤哈希即可。哈希：第⼀个数是base的n次⽅，依次递减，最后⼀个数是base的0次⽅。 base是任意的⼀个数，但是base必须⼤于字符集中转换后的值中最⼤的⼀个，并且是质数。 关于base的n⽅的实现：先让前⼀个数乘base,然后再加上当前的值,⽤记录的值再乘base，. 便能得到n⽅。 哈希求两段之差时：需要把前⾯的段乘上中间所差的段的次⽅，是为了同级，但是少的值， 仍然存在。哈希数学表⽰：哈希代码实现：

完整代码：#include using namespace std;#define int long longconst int mod=1e9+7;const int P=9999971,base=101;const int N=2e5+10;char a[N],b[N];int ha[N],hb[N],hc[N];signed main() { ios_base::sync_with_stdio(false); (NULL); int n,m; cin>>n>>m; cin>>a+1>>b+1; hc[0]=1; for(int i=1;i<=n;i++) { hc[i]=(hc[i-1]*base)%P; } for(int i=1;i<=n;i++) { ha[i]=(ha[i-1]*base+a[i]-'a')%P; } for(int i=1;i<=m;i++) { hb[i]=(hb[i-1]*base+b[i]-'a')%P; } int ans=0; for(int i=1;i+m-1<=n;i++) { if((ha[i+m-1]-ha[i-1]*hc[m]%P+P)%P==hb[m])ans++;//*hc[m]是为了同级，但是少的值仍然存在 } cout<