第一题ac代码

k = int(input().strip())
A = input().strip()
B = input().strip()

la = len(A)
lb = len(B)
def getnext(ps):
nextarr = [-1 for i in range(len(ps))]
nextarr[0] = -1
j=0
k=-1
while j<len(ps)-1: if k==-1 or (k>=0 and ps[j]==ps[k]):
j+=1
k+=1
if ps[j] == ps[k]:
nextarr[j] = nextarr[k]
else:
nextarr[j] = k
else:
k = nextarr[k]
return nextarr

def kmp(ts,ps):#
i,j = 0,0 # i : zhuchuan
nextarr = getnext(ps)
count = 0
while i<len(ts):

    if (j==-1 or ts[i]==ps[j]):
        i+=1
        j+=1
    else:
        j = nextarr[j]
    if j == len(ps):
        i = i-j+1
        j=0
        count+=1

return count

zichuan = {}
i = 0
res = 0
while i < la-k+1:
cur = A[i:i+k]
if cur not in zichuan:
zichuan[cur] = 1
count = kmp(B,cur)
res+=count
i+=1
print(res)