题解 | String Matching

def getNext(s):
    next = [0] * len(s)
    next[0] = 0
    j = 0
    for i in range(1, len(s)):
        while j > 0 and s[i] != s[j]:
            j  = next[j-1]
        if s[i] == s[j]:
            j += 1
        next[i] = j
    next.insert(0, -1)
    return next

def kmp(s, t):
    i = 0
    j = 0
    next = getNext(t)
    #print(next)
    s = list(s)
    t = list(t)
    res = 0

    while i < len(s) and j < len(t):
        if (j == -1 or s[i] == t[j]):
            j += 1
            i += 1
        else:
            j = next[j]
        if j == len(t):
            res += 1
            j = next[j] 
    return res

s, t = input().split()
print(kmp(s, t))