D题 通过率64% 求助

lst 记录每个Hash上次的位置 cnt 记录每个Hash 已有的个数

#include<map>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000017
#define ull unsigned long long
using namespace std;
map<ull,int>lst;map<ull,int>cnt;int n,m,k;ull mul[N];char s[N];
int main()
{
	scanf("%d%d%d",&n,&m,&k);scanf("%s",s+1);
	mul[0] = 1;
	for(int i = 1;i < m;i += 1)mul[i] = mul[i-1] * 131;
	int ans = 0;ull Hash = 0;
	for(int i = 1;i <= m;i += 1)Hash = Hash * 131 + s[i]-'0';
	cnt[Hash]++,lst[Hash] = m;
	if(cnt[Hash] == k)ans++;
	for(int i = m+1;i <= n;i += 1){
		Hash = Hash - mul[m-1]*(s[i-m]-'0');
		Hash = Hash * 131 + s[i]-'0';
		if(!cnt[Hash])cnt[Hash]++,lst[Hash] = i;
		else if(i-lst[Hash]+1 > m)cnt[Hash]++,lst[Hash] = i;
		if(cnt[Hash] == k)ans++;
		else if(cnt[Hash] > k)ans--;
	}
	printf("%d\n",ans);
	return 0;
}