题解 | #kmp算法#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
class Solution:
    def kmp(self, S: str, T: str) -> int:
        # write code here
        m, n = len(S), len(T)
        j = 0
        result = 0
        #生成next数组
        next = self.get_next(S)
        for i in range(n):
            #如果不匹配，将模式串指针回退，回退next[j-1]
            while j > 0 and S[j] != T[i]:
                j = next[j - 1]
            #匹配成功，模式串指针+1
            if S[j] == T[i]:
                j += 1
            #完全匹配，记录次数，并回退到next[j-1]重新开始匹配
            if j == m:
                result += 1
                j = next[j - 1]
        return result
	#计算next数组
    def get_next(self, S: str):
        m = len(S)
        #初始化next数组为全0
        next = [0 for _ in range(m)]
        #left代表前缀开始所在的下标位置
        left = 0
        #right代表后缀开始所在的下标位置
        for right in range(1,m):
            #匹配不成功，left回退，当left==0时，停止回退
            while left > 0 and S[left] != S[right]:
                left = next[left - 1]
            #匹配成功，left+1
            if S[left] == S[right]:
                left += 1
            #记录前缀长度，更新next[right]，结束本次
            next[right] = left
        return next