题解

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=1e6+100;
const int p=998244353;
string s0,s1;
int n,m;
int ans;
int pw[N],hsh[N],llooll;
int gethsh(int l,int r){return hsh[r]-hsh[l-1]*pw[r-l+1];}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s0>>s1;
    s0=" "+s0,s1=" "+s1;
    pw[0]=1; 
    for(int i=1;i<=n;i++) {
    	pw[i]=pw[i-1]*p;
    	hsh[i]=hsh[i-1]*p+s0[i];
	}
	for(int i=1;i<=m;i++) llooll=llooll*p+s1[i];
	for(int i=1;i<n-m+1;i++) {
		if(gethsh(i,i+m-1)==llooll) i+=m;
//		cout<<i<<'\n';
		ans++;
	}
	if(gethsh(n-m+1,n)==llooll) ans++;
	else ans+=m;
	cout<<ans;
	return 0;
}