题解 | #kmp算法#

# 【最浅显易懂的 KMP 算法讲解-哔哩哔哩@奇乐编程学院】 https://b23.tv/10QofYa
#  评论区找到@v2df_t 于23年8月18日关于 prefix_len = next[prefix_len - 1] 的解释
#  阮一峰的图解文章（13年五一）：https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
class Solution:
    def kmp(self , S: str, T: str) -> int:
        len_t = len(T)
        len_s = len(S)
        if len_t < len_s:
            return 0
        count = 0
        next = self.build_partmatch(S)
        t = 0 # 主串指针
        s = 0 # 模板串指针
        while t < len_t: # 精髓/目的就是主串一次遍历
            if T[t] == S[s]:
                s += 1
                t += 1
                if s == len_s: # 模板串完全匹配完
                    count += 1
                    s = next[s - 1]
                    # s -= s - next[s - 1] # 公式：移动位数=已匹配的字符数-对应部分匹配值
            elif s > 0: # 非模板串首位不匹配则借助部分匹配表仅右滑模板串再试试
                s = next[s - 1]
            else: # 模板串首位不匹配则右滑主串，模板串指针先保留成果下个while试试、不行则再进elif去右滑模板串
                t += 1
        return count

    def build_partmatch(self, pattern):
        next = [0]
        for i in range(1, len(pattern)): # 求剩余各个部分匹配值
            k = next[i - 1]
            while k > 0 and pattern[i] != pattern[k]:
                k = next[k - 1] # 滚起来的杀人书一旦被终结就是递推坍缩（理解为逆向斐波拉契数列）
            if pattern[i] == pattern[k]: # 结束循环的2种情况之一：匹配到了
                k += 1 # 在当前成果上加上自己这位字符（数）
            next.append(k) # 省略了else: 如果一直不匹配，直至k = next[0] == 0
        return next
# 以下为测试用例，供VSCode中调试使用
if __name__ == '__main__':
    solution = Solution()
    S = "ababab"
    T = "abababab"
    result = solution.kmp(S,T)
    print(result)