题解 | #kmp算法#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        
        # 1.求next数组
        # next的值就是每一位的最长公共前后缀的大小
        len_S = len(S)
        next = [-1] * len_S   # 初始化next
        # 长度为1则直接跳过
        if len_S != 1:
            next[0] = -1
            next[1] = 0
            i = 2
            re = next[i-1]  # re表示next[k-1]，初始化为next[i-1]
            # 遍历S
            while i < len_S:
                # 若相同，输出并继续遍历
                if re != -1 and S[i-1] == S[re]:
                    next[i] = re + 1
                    re = next[i]
                    i += 1
                # 若不同且re不指向-1，指向下一个re
                elif re != -1 and S[i-1] != S[re]:
                    re = next[re]
                # 若re指向-1，输出0并继续遍历
                else:
                    next[i] = 0
                    re = next[i]
                    i += 1
		
        # 2.求出现次数
        count = 0   # 计数器
        j = 0   # 指向S下标的指针
        i = 0   # 指向T下标的指针
        # 循环遍历T
        while i < len(T):
            # 若不匹配，用next[j]再进行匹配，直到匹配或j指向-1
            while S[j] != T[i] and j >= 0:
                j = next[j]
            # 若S最后一位匹配，匹配next[j]，并计数一次
            if j == len(S)-1:
                j = next[j]
                count += 1
                continue
            # 若非S最后一位匹配，匹配下一位
            # 若j指向-1，匹配下一位
            j += 1
            i += 1
        return count