代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

计算模板串S在文本串T中出现了多少次

@param S string字符串 模板串

@param T string字符串 文本串

@return int整型

def kmp(self , S: str, T: str) -> int:
    if S == '': return 0
    n = len(S)
    m = len(T)
    j = 0
    pnext = self.getnext(S)
    res = []
    for i in range(m):
        while j > 0 and S[j] != T[i]:
            j = pnext[j] #对应位置不匹配就一直回溯，直到回溯到0
        if S[j] == T[i]:
            j += 1    #如果对应位置相等就前进
        if j == n:
            res.append(i-n+1)  #直到和S等长，把这个初始位置记录到res里
            j = pnext[j] #这步相当于再回溯，其实是为了继续找新的pattern
    return len(res)

   
    
#建立一个pnext回溯前缀表,指S里的前缀和后缀拆分到底以后有多少相同的元素
def getnext(self, s):
    n = len(s)
    pnext = [0, 0]  #没太理解网上教的-1之类的，初始化两个0，因为前两位是不可能有其他值的
    j = 0           #如果只初始化一个0，在匹配函数里j = -1
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = pnext[j] # s[j] != s[i]的话j一直是0位，等待相等了以后再往出走
        if s[j] == s[i]:
            j += 1
        pnext.append(j)
    return pnext
    # write code here