KMP 算法

KMP有什么用

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

例子：要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

可以看出，文本串中第六个字符b 和模式串的第六个字符f，不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。

但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。

理解：在当前对文本串和模式串检索的过程中，若出现了不匹配，如何充分利用已经匹配的部分。到不匹配时，找到匹配的字符串中，最长的相等的前后缀。例如上面的例子，已经匹配了 aabaa，下一个不匹配了，找到最长相等的前后缀为 aa。这个 aa 表示：

模式串的前两个 aa
匹配了的文本串的后两个 aa

这两个部分是相等的，所以这两部分不用匹配，直接从 aa 的下一个字符开始匹配，如图所示：

next 数组

参考讲解 bilibili，以及其中的评论：

借视频中例子说明一下 prefix_len = next【prefix_len - 1】的原因。
例如，串 A B A C A B A B
　　　　 0 1 2 3 4 5 6 7
扫描到 6 号位的 A 时，最长公共前后缀是 ABA；而扫描到 7 号位的 B 时，ABAC 和 ABAB 不匹配了，即原来的最长公共前后缀失配。这时候我们要做的事情就是，找上一次匹配中次长的公共前后缀，看与 7 号位的 B 拼接起来是否能匹配。
这时候，注意到上一次扫描中 0 ~ 2 位的 ABA 是和 4 ~ 6 位的 ABA 完全相同的（贪心原则保证上次结果一定是包含前一位置字符的最长公共前后缀），所以考察上一次匹配中次长的公共前后缀，只能在考察上一次匹配中的最长公共前后缀中考察，也就是说，只能考察 ABA 中更短的 BA、A 是否是次长的，而这直接在前面一个 ABA 中考察都行，所以我们把 ABA C ABA 中中间部分（C）和后缀（ABA）直接抛弃，等效于一个串 ABA（也就是前缀）与 B 拼接成 ABAB。这样再来计算第 7 位的 B 的 next 值，等价于计算 ABAB 第 3 位的 B 的 next 值。prefix_len = next【prefix_len - 1】也就是这个等效过程的代码展示。

next 数组表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

在比较时找到的不匹配的位置，那么此时我们要看它的前一个字符的前缀表的数值是多少。然后移动到前缀表数值对应的下标处重新开始匹配。

如何计算 next 数组？核心是“回退”，利用前面计算好的 next 数组来简化计算。可以分为三个步骤：

初始化
字符相同时
字符不同时

初始化

初始化两个指针，i 表示后缀的末尾，从 1 开始；j 表示前缀的末尾（也表示前缀的长度），从 0 开始。最开始 next[0] 一定为 0，因为没有意义。然后 i 遍历 range(1, len(patt))。分别处理相同和不相同的情况。（先理解后面两种情况，然后再理解为什么这样初始化）

字符相同

例如，已经找到了当前最长的相同前后缀为 AB，此时 j=1（B），i=5（B）。在下一轮，我们只需要判断下一个字符是否相同，即 j=2（A），i=6（B），此时相同，那么就可以直接将前缀长度 j（也等于 next[i-1]，但是为了统一表达，还是使用 j，详见下面的情况）加一作为当前的 next[i]。

字符不同

上一步已经找到最长的相同前后缀为 ABA，但是下一个字符不相同。此时要做的事情是，找上一次匹配中次长的相同前后缀，看与 i=7 的 B 拼接起来是否能匹配（因为要使用之前计算的 next 数组，最长的不符合就找次长的）。

而找次长的相同前后缀，等价以当前最长的相同前后缀为对象，找最长的相同前后缀。（也就是将 ABA 看作单独的字符串，找 ABA 的最长相同子字符串）。因为次长的相同前后缀一定在最长的前后缀中（贪心原则，每次都是在上一轮最长前后缀的基础上扩展）。

而 ABA 的最长相同前后缀在之前已经计算好了，为 next[j-1]（此时 j=3）（左图）。所以 j 就回退到次长的相同前后缀处（回退后 j=1），再次进行比较（中图）。此时字符相同，就可以直接将前缀长度 j 加一作为当前的 next[i]（右图，注意，此时就不能再像上面那个情况一样，使用 next[i-1] 来赋值）。

计算 next 数组

在遍历 i 时，注意 for 和 while 循环的不同写法。因为在字符不相同时，j 需要回退到次长相同前后缀的位置来再次比较，如果还是不相同还需要回退。所以 i 的值需要手动控制（使用 while 循环）或者对当前 i 进行多次比较（for 循环中再套一层 while）。代码如下：

i = 1
j = 0
next = [0] * len(patt)

while i < len(patt):
    if patt[i] == patt[j]:
        next[i] = j + 1
        j += 1
        i += 1
    else:
        if j == 0:
            next[i] = j
            i += 1
        else:
            j = next[j - 1]

j = 0
next = [0] * len(patt)

for i in range(1, len(patt)):
    while j > 0 and patt[i] != patt[j]:
        j = next[j-1]
    if patt[i] == patt[j]:
        j += 1
    
    next[i] = j

28. 实现 strStr()

link

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

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

思路

KMP 算法的应用，计算完 next 数组后，就需要进行匹配。使用两个指针，分别在文本串和模式串上移动，当不匹配时，模式串上的指针 j 就回退到前一位对应的 next 数组的值处，即 j = next[j-1]。（从这里也可以看出，计算 next 数组本质上也是 KMP 算法！）

注意两种写法的返回值不一样！

for 写法：i 是在每次循环开始才增加，在循环中，j 先增加，所以判断是否遍历到模式串末尾时，只有 j 增加了，所以返回需要加 1。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        j = 0
        next = [0] * len(needle)

        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = next[j-1]
            if needle[i] == needle[j]:
                j += 1
            
            next[i] = j
        
        j = 0
        i = 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 - j + 1
    return -1

while 写法：while 循环是我们自己控制 i 和 j 的增减，所以如果满足条件，他们是同时增加的。所以判断是否遍历到模式串末尾时，不需要加 1。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        j = 0
        next = [0] * len(needle)

        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = next[j-1]
            if needle[i] == needle[j]:
                j += 1
            
            next[i] = j
        
        j = 0
        i = 0
            
        while i < len(haystack):
            if haystack[i] == needle[j]:
                j += 1
                i += 1
            else:
                if j == 0:
                    i += 1
                else:
                    j = next[j-1]

            if j == len(needle):
                return i - j 

        return -1

459. 重复的子字符串

link

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:

输入: s = “aba”
输出: false

思路 1

对每个子串都应用 KMP 算法，优化的点：

传入的 haystack 串可以去除选择的子串
遍历子串的时候，如果剩余长度小于子串长度，则跳过
return 的时机：
- 不相等直接 return False
- 两个指针同时指向各自字符串的末尾

但是会超出时间限制

class Solution:

    def kmp(self, haystack, needle):
        j = 0
        next = [0] * len(needle)

        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = next[j-1]
            if needle[i] == needle[j]:
                j += 1
            
            next[i] = j
        
        j = 0
        i = 0
            
        while i < len(haystack):
            if haystack[i] == needle[j]:
                j += 1
                i += 1
            else:
                return False

            if j == len(needle):
                if i == len(haystack):
                    return True
                else:
                    j = 0


    def repeatedSubstringPattern(self, s: str) -> bool:
        for i in range(len(s)):
            left = len(s) - i - 1
            if left < i + 1:
                return False
            
            if self.kmp(s[i+1:], s[0:i+1]):
                return True

思路 2：暴力

一个for循环获取子串的终止位置，然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。

思路 3：移动匹配

如果一个字符串 s 由子串构成，那么 s+s 去掉首尾之后一定包含 s。

需要证明充要性:（？）

s 可由某个非空子串重复 k≥2 次构成 <–> s 是 (s+s)[1:−1] 的一个子串.

可以直接用 in，也可以用 KMP 实现的 strStr()。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        j = 0
        next = [0] * len(needle)

        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = next[j-1]
            if needle[i] == needle[j]:
                j += 1
            
            next[i] = j
        
        j = 0
        i = 0
            
        while i < len(haystack):
            if haystack[i] == needle[j]:
                j += 1
                i += 1
            else:
                if j == 0:
                    i += 1
                else:
                    j = next[j-1]

            if j == len(needle):
                return True

        return False
    def repeatedSubstringPattern(self, s: str) -> bool:
        
        ss = s + s
        return self.strStr(ss[1:-1], s)

思路 4：KMP

在一个串中查找是否出现过另一个串，这是KMP的看家本领。KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。那么最长相同前后缀和重复子串的关系又有什么关系呢？

字符串s是由重复子串组成 <===> 最长相等前后缀不包含的子串是字符串s的最小重复子串