题解 | #小Why的密码锁#

枚举所有长度为 m 的子串作为可能密码，用双哈希区分子串。对每种密码按出现位置贪心统计不重叠出现次数，次数正好为 k 的密码就是答案。

import sys

MOD=1000000007
MOD2=998244353
def solve():
    n,m,k=int(next(it)),int(next(it)),int(next(it))
    s=next(it)
    b=911382323
    x=pow(b,m-1,MOD)
    y=pow(b,m-1,MOD2)
    h=g=0
    for c in s[:m]:
        v=ord(c)-47
        h=(h*b+v)%MOD
        g=(g*b+v)%MOD2
    d={}
    for i in range(n-m+1):
        z=(h<<30)|g
        if z not in d:
            d[z]=[1,i]
        else:
            v=d[z]
            if v[0]<=k and i-v[1]>=m:
                v[0]+=1
                v[1]=i
        if i<n-m:
            a=ord(s[i])-47
            c=ord(s[i+m])-47
            h=((h-a*x)*b+c)%MOD
            g=((g-a*y)*b+c)%MOD2
    print(sum(v[0]==k for v in d.values()))

if __name__=="__main__":
    it=iter(sys.stdin.read().split())
    _=1
    #_=int(next(it))
    for __ in range(_):
        solve()