单哈希

//单哈希
#include<bits/stdc++.h>
using namespace std;

const int p = 9999971,base = 137,N = 200011;

int n,m,ha[N],hb[N],c[N];
char a[N],b[N];

int main () {

    scanf("%d%d",&n,&m);
    scanf("%s %s",a+1,b+1);
    c[0] = 1;
    for(int i=1;i<=200000;i++) {
        c[i] = c[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] - 1LL * ha[i-1] * c[m] %p + p) % p == hb[m])
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

双哈希

#include<bits/stdc++.h>
using namespace std;

const int p = 9999971,base = 101;
const int N = 200011;
const int base2 = 137,p2 = 9999973;

int n,m;
int ha[N],hb[N],c[N];
int c2[N],ha2[N],hb2[N];
char a[N],b[N];

int main () {

    scanf("%d%d",&n,&m);
    scanf("%s %s",a+1,b+1);
    c[0] = 1;c2[0] = 1;
    for(int i=1;i<=200000;i++) {
        c[i] = c[i-1] * base % p; 
        c2[i] = c2[i-1] * base2 % p2; 
    }

    for(int i=1; i<=n; i++) {
        ha[i] = (ha[i-1] * base + a[i] - 'a') % p;
        ha2[i] = (ha2[i-1] * base2 + a[i] - 'a') % p2;
    }

    for(int i=1; i<=m; i++) {
        hb[i] = (hb[i-1] * base + b[i] - 'a') % p;
        hb2[i] = (hb2[i-1] * base2 + b[i] - 'a') % p2;
    }

    int ans = 0;
    for(int i=1; i+m-1 <= n; i++) {
        if(((ha[i+m-1] - 1LL * ha[i-1] * c[m] %p + p) % p == hb[m])
            &&((ha2[i+m-1] - 1LL * ha2[i-1] * c2[m] %p2 + p2) % p2 == hb2[m]))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}