题解 | #kmp算法#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
class Solution:

    
    def kmp(self , S , T ):
        def get_next(p):
            n = [-1] * (len(p)+1) // 并行多加1，因为需要匹配多次
            k = -1
            j = 0
            while j < len(p):
                if k == -1 or p[j] == p[k]:
                    k +=1
                    j +=1
                    n[j] = k
                else:
                    k = n[k]


            return n
        
        next_arr = get_next(S)
        j = 0
        result = 0
        i = 0
        while i < len(T):
            if j == -1 or T[i] == S[j]:
                i +=1
                j +=1
            else:
                j = next_arr[j]
                
            if j == len(S):
                result +=1
                j = next_arr[j]
            
                
        return result