KMP算法

主要应用

应用在字符串匹配上

主要思想

当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

一些基本概念

前缀表：用来回退，当模式串与主串(文本串)不匹配的时候，模式串应该从前面哪里开始重新匹配。即 next 数组
例如：

求模式串aabaaf的前缀表
a -> 0
aa -> 01
aab -> 010
aaba -> 0101
aabaa -> 01012
aabaaf -> 010120

求next数组

求next数组，有两种实现方式
1.原next数组当作前缀表
2.原next数组每个元素统一减去1后当作前缀表

# 第一种
def getNext(nxt: List[int], s: str):
    nxt[0] = 0
    j = 0
    for i in range(1, len(s)):
        while j > 0 and s[i] != s[j]:
            j = nxt[j-1]
        if s[i] == s[j]:
            j += 1
        nxt[i] = j
    return nxt

注意：

• next数组的第一个字符的值为0
• j表示的是字符串s中，当前字符s[i]的最长公共前后缀，即next数组中的值
• for循环是从第二个字符开始的，因为第一个字符永远设置为0
• while循环，当前字符不匹配了，就往前找最近的匹配字符；同时需要保证j>0
• 当前字符匹配时，j的值+1，并保存在next数组对应的位置i中

# 第二种
def getNext(nxt: List[int], s: str):
    nxt[0] = -1
    j = -1
    for i in range(1, len(s)):
        while j >= 0 and s[i] != s[j]:
            j = nxt[j]
        if s[i] == s[j+1]:
            j += 1
        nxt[i] = j
    return nxt

找出字符串中第一个匹配项的下标

leetcode 28
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

# 使用原next数组
class Solution:
    def getNext(self, nxt, s: str):
        nxt[0] = 0
        j = 0
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = nxt[j-1]
            if s[i] == s[j]:
                j += 1
            nxt[i] = j
        return nxt

    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        nex = [0]*len(needle)
        next = getNext(nex, needle)
        j = 0
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = next[j-1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):            # 此时，匹配成功
                return i - len(needle) + 1  # 主串匹配到了第i+1个字符，故减去模式串的长度，即为第一个匹配项的首字母下标
        return -1

# strStr('sadssasad', 'sas')
# next = [0, 0, 1] 
# 输出 4

References

• 代码随想录