说明

快速匹配相同的子字符串

代码模版

模版1

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def KMP(s, p):
            """
            s为主串
            p为模式串
            如果t里有p，返回打头下标
            """
            nex = getNext(p)
            i = 0
            j = 0   # 分别是s和p的指针
            while i < len(s) and j < len(p):
                if j == -1 or s[i] == p[j]: # j==-1是由于j=next[j]产生
                    i += 1
                    j += 1
                else:
                    j = nex[j]

            if j == len(p): # j走到了末尾，说明匹配到了
                return i - j
            else:
                return -1

        def getNext(p):
            """
            p为模式串
            返回next数组，即部分匹配表
            """
            nex = [0] * (len(p) + 1)
            nex[0] = -1
            i = 0
            j = -1
            while i < len(p):
                if j == -1 or p[i] == p[j]:
                    i += 1
                    j += 1
                    nex[i] = j     # 这是最大的不同：记录next[i]
                else:
                    j = nex[j]

            return nex
        
        return KMP(haystack, needle)

模版2

def KMP(s: str, p: str) -> List[int]:
    ans = []
    x = p + '#' + s
    pi = [0] * len(x)
    for i in range(1, len(x)):
        j = pi[i-1]
        while j > 0 and x[i] != x[j]:
            j = pi[j-1]
        if x[i] == x[j]:
            j += 1
        pi[i] = j
        if pi[i] == len(p):
            ans.append(i - 2 * len(p))
    return ans