kmp

def prep(p):
    pi = [0] * len(p)
    j = 0
    for i in range(1, len(p)):
        while j != 0 and p[j] != p[i]:
            j = pi[j - 1]
        if p[j] == p[i]:
            j += 1
        pi[i] = j
    return pi

匹配：
$ 仅作为标识符，分割战场。这段代码的作用是在 nums 中找到有多少个 p。

return prep(p + '$' + nums).count(len(p))

z函数

Z函数作用：返回一个数组，数组里是每个位置跟原字符串的最长公共前缀长度。O(n)。

def z_function(s: str) -> List[int]:
        n = len(s)
        z = [0] * n
        z[0] = n
        l = r = 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(z[i - l], r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                l, r = i, i + z[i]
                z[i] += 1
        return z

匹配:

m = len(p)
return sum(lcp == m for lcp in z_function(p + ['$'] + nums)[m + 1:])