【无标题】

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

小Why拿到了一个密码长度为 mmm 的密码锁，这个密码锁可输入内容无限，并只对最后输入的 mmm 位字符进行检测，检测正确时密码锁会解锁一次，同时清空包含检测正确字符串在内的之前的所有字符。

小Why输入了一个长度为 nnn 的字符串 sss 后，密码锁一共解锁了 kkk 次，请你告诉他有多少种密码是可能正确的。

输入描述:

第一行包含三个整数 n,m,k (1≤m∗k≤n≤106)n,m,k \ (1 \leq m*k \leq n \leq 10^6)n,m,k (1≤m∗k≤n≤106)，表示字符串 sss 的长度，密码长度和解锁次数。

第二行包含一个长度为 n \ n \  n 的字符串 sss，保证字符串 sss 中只含有 0∼90\sim90∼9 的数字。

---

分析：

  字符串哈希unsigned long long类型

---

#include<bits/stdc++.h>
typedef long long ll;
#define ull unsigned long long
using namespace std;
const ll N=1e6+3;
const ull mod=1313;
ull p[N],h[N];
ull get(ll l,ll r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
void solve()
{
  memset(p,0,sizeof p);
  memset(h,0,sizeof h);
  ll n,m,k;
  cin>>n>>m>>k;
  map<ull,ull> hash,la;
 string s;
    cin>>s;
    s=" "+s;
  p[0]=1;
  for(ll i=1;i<=n;i++)
  {
      p[i]=p[i-1]*mod;
      h[i]=mod*h[i-1]+s[i];
  }
  for(ll i=1;i+m-1<=n;i++)
  {
      ull res=get(i,i+m-1);
      if(la[res]&&la[res]+m-1>=i)continue;
      la[res]=i;
      hash[res]++;
  }
  ull sums=0;
  for(auto [uu,vv]:hash)
  {
      if(vv==k)sums++;
  }
  cout<<sums<<'\n';
}
    int main()
   {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--)
    solve();
    return 0;
    }