题解 | #kmp算法#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        def next_cal(S):
            prefix = 0
            m = len(S)
            next_val = [0]
            for i in range(1,m):
                if S[i]==S[prefix]:
                    prefix+=1
                elif prefix>0:
                    prefix = next_val[prefix-1]
                next_val.append(prefix)
            return next_val
        
        cnt = 0
        i,j = 0,0
        m,n = len(S),len(T)
        next_val = next_cal(S)
        while(i<n):
            if T[i]==S[j]:
                i+=1
                j+=1
                if j==m:
                    cnt+=1
                    j = next_val[j-1]
            elif j>0:
                j = next_val[j-1]
            else:i+=1
        return cnt

对原本的KMP算法增加了记录数量的功能，其实就是把主函数中：j到数组末端的时候认为“不匹配”，然后触发原本KMP算法中的j的回退：j = next[j-1]就可以了，每当j到达patt串末端，都使得计数结果res+1，最后返回res