小Why的密码锁【牛客tracker 每日一题】
小Why的密码锁
时间限制：3秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小W h y WhyWhy拿到了一个密码长度为m mm的密码锁，这个密码锁可输入内容无限，并只对最后输入的m mm位字符进行检测，检测正确时密码锁会解锁一次，同时清空包含检测正确字符串在内的之前的所有字符。
小W h y WhyWhy输入了一个长度为n nn的字符串s ss后，密码锁一 共解锁了k kk次，请你告诉他有多少种密码是可能正确的。
输入描述：
第一行包含三个整数n , m , k ( 1 ≤ m ∗ k ≤ n ≤ 10 6 ) n,m,k (1≤m∗k≤n≤10^6)n,m,k(1≤m∗k≤n≤106)，表示字符串s ss的长度，密码长度和解锁次数。
第二行包含一个长度为n nn的字符串s ss，保证字符串s ss中只含有0 ∼ 9 0 ∼ 90∼9的数字。
输出描述：
输出一个整数，表示有多少种密码是可能正确的。
示例1
输入：
13 5 2 1231234123123输出：
2说明：
一种可能正确的密码是“ 23123 ” “23123”“23123”：当输入到第6 66位时密码锁第一次解锁，“ 123123 ” “123123”“123123”被全部清空；当输入到第13 1313位时密码锁第二次解锁，“ 4123123 ” “4123123”“4123123”被全部清空。
解题思路
本题核心是字符串哈希预处理 + 合法密码规则校验，高效解决百万级长度字符串的匹配计数问题。根据密码锁解锁规则：合法密码必须在字符串中恰好出现k次，且每次匹配的起始位置 ≥ 上一次匹配的结束位置+1（解锁后清空字符，后续匹配必须从新位置开始）。使用前缀哈希将所有长度为m的子串转化为哈希值，实现O(1)快速查询对比。遍历所有候选子串，用哈希表记录每个密码的上一次结束位置和出现次数，过滤非法匹配。最终统计出现次数恰好为k的密码数量，即为答案。算法时间复杂度O(n)，完美适配n≤1e6的大数据约束。
总结
核心逻辑：合法密码需恰好匹配k次，且匹配位置满足解锁清空的间隔要求。
关键操作：前缀哈希快速计算子串哈希值、哈希表记录密码的位置与次数、筛选合法密码。
效率保障：线性预处理+线性遍历，常数级哈希查询，无冗余运算，轻松处理百万级字符串。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e6+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll P=131;chara[N];ll n,m,k;ll p[N],h[N];llget(ll l,ll r){returnh[r]-h[l-1]*p[r-l+1];}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);map<ll,ll>lst,cnt;cin>>n>>m>>k;cin>>a+1;p[0]=1;for(ll i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+a[i];}for(ll i=1;i<=n-m+1;i++){ll hs=get(i,i+m-1);if(lst[hs]+m-1>=i&&lst[hs])continue;lst[hs]=i;cnt[hs]++;}ll ans=0;for(autoit:cnt)if(it.second==k)ans++;cout<<ans<<endl;return0;}