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; }