题解 | #kmp算法#

空间复杂度O(len(S)，时间复杂度 O(len(S)+len(T))

【最浅显易懂的 KMP 算法讲解】https://www.bilibili.com/video/BV1AY4y157yL

from sys import prefix
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        s = len(S)
        t = len(T)
        if (s > t or t == 0):
            return 0

		def getNext(S):
            s = len(S)
            next = [0] # 初始值为0
            prefix_len = 0 # 最长公共前后缀长度，常写为j
            i = 1
            while i < s:
                # 当前字符依旧相同，可以生成更长的前后缀
                if S[prefix_len] == S[i]:
                    prefix_len += 1
                    next.append(prefix_len)
                    i += 1
				# 当前字符不相同，查看有无次长的前后缀
                else:
					# 不存在设为0
                    if prefix_len == 0:
                        next.append(0)
                        i += 1
                    else:
						# 直接去找以前算过的次长前后缀去比较
                        prefix_len = next[prefix_len-1]
            return next
			
        cnt = 0
        next = getNext(S)

		# i是T的索引，j是S的索引
        j = 0 
        for i in range(t):
			# 不匹配就找次长前后缀去比较
            while(j > 0 and S[j] != T[i]):
                j = next[j-1]
            # 相等往前推
            if (S[j] == T[i]):
                j += 1
            # 匹配成功次数加一
            if (j == s):
                cnt += 1
                j = next[j-1]
        return cnt