题解 | #String Matching#

def getNext(t):
    next = [0] * (len(t)+1)
    t = list(t)
    i, k = 0, -1
    next[0] = -1
    while i < len(t):
        if k == -1 or t[i] == t[k]:
            k+=1
            i+=1
            next[i] = k
        else:
            k = next[k]
    return next

def kmp(s, t):
    i, j = 0, 0
    res =0
    next = getNext(t)
    s = list(s)
    t = list(t)
    while i < len(s) and j < int(len(t)):
        if(j == -1 or s[i] == t[j]):
            i+=1
            j+=1
        else:
            j = next[j]

        if j == len(t):
            res+=1
            j = next[j]
            #return i - j
    return res
   

# while True:
#     try:
s, t = input().split()
res = kmp(s, t)
print(res)
    # except:
    #     break