超简单理解KMP算法（最长公共前后缀next数组、合并主子串、子串偏移法）

参考b站：子串偏移、合并主子串

最长公共前后缀next

这个概念是一个trick，帮助我们记录遍历了一遍的数组的相似特性，想出来确实很nb，我也不理解逻辑是怎么想出来的。
字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
例如，对于字符串 "ababc"：

• 前缀有："a", "ab", "aba", "abab"，第一个字符一定会有
• 后缀有："c", "bc", "abc", "babc"，最后一个字符一定会有

最长公共前后缀：指某个字符串的前缀和后缀中相等的最长子串。例如：

• 对于 "abab"，最长公共前后缀是 "ab"，长度为 2。
• 对于 "abc"，没有公共前后缀，长度为 0。

例如，对于模式串 "ababc"，其前缀表为 [0, 0, 1, 2, 0]：

• 第 0 位："a"，没有前后缀，值为 0。
• 第 1 位："ab"，没有公共前后缀，值为 0。
• 第 2 位："aba"，最长公共前后缀为 "a"，值为 1。
• 第 3 位："abab"，最长公共前后缀为 "ab"，值为 2。
• 第 4 位："ababc"，没有公共前后缀，值为 0。

现在我们希望在一次遍历字符串的过程中记录该字符串的相似性质，该如何计算最长公共前后缀的数组，通常被称为next？用递推的性质：
假设我们希望求next[i]，并知道红色段next[i-1]=len，那说明[0,i-1]的子串的首尾均有长度为len的前后缀

• 如果str[i]==str[len]，说明[0,i]的子串的首尾均有len+1长度的前后缀，得到next[i] =len+1（注意下标从0开始所以比较的是str[len]）

• 如果str[i]!=str[len]，我们继续寻找[0,i-1]的子串中第二长、第三长的前缀串粉色段，这些字符串虽然长度小于len，但起点和终点依然是0和j-1，因为next[i]找到的前后缀一定要经过0和j
  
• 把寻找的过程可以写成while，目标是找到尽量长的粉色段n，并满足str[n]=str[i]
• 现在问题是n怎么获得？我们最初知道next[i-1]=len，所以绿色=橙色，而现在又找到了蓝色=橙色，所以有蓝色=绿色，所以粉色段恰恰可以用next[len-1]表示，当找到了粉色段但不满足str[n]=str[i]时，继续找下一个粉色段，即next[n-1]，如此循环
  
• 最终可以得到next数组，方法如下：

vector<int> pi(str.size());
for (int i = 1; i < str.size(); i++) {int len = pi[i-1];while (len != 0 && str[i] != str[len]) {len = pi[len - 1];}if (str[i] == str[len]) {pi[i] = len + 1;}
}

合并主子串

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
把haystack 和 needle合并，中间用#分隔，求合并串的next数组，如果数组中有值等于len(needle)，则说明有匹配项

这种方法可以直接在next数组获得的过程中判断，代码如下：

class Solution:def strStr(self, haystack: str, needle: str) -> int:n = len(haystack) #主串的的长度m = len(needle) #子串的长度if haystack == needle: #因为i从1开始，所以处理edge casereturn 0s = needle + "#" + haystack #注意把子串放前面，这样前缀和才能覆盖子串next = [0] * len(s)for i in range(1, n + m + 1): #注意+1是因为"#"多了一位len_ = next[i - 1]while len_ != 0 and s[i] != s[len_]: #等于0也是没有，会跳过的len_ = next[len_ - 1]if s[i] == s[len_]: #跳出循环要不是0要不相等next[i] = len_ + 1if next[i] == m:#返回第一个return i - m*2 #合并串从第m+1位开始才是主串，所以主串中开始匹配的下标是i - (m+1) - m + 1=i-2*mreturn -1

子串偏移

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
子串偏移方法一句话就是利用子串的前后缀和，保证下一个可能匹配的地方就是主串的后缀。

• 比如第i位AC虽然没有匹配上，但我们知道[0,i-1]的内容是一样的，如何复用这一信息？注意i指的是子串指针，这里图示主串和子串指针是一样的所以没有区分，但本质要利用子串next数组的前后缀相同，所以要用子串指针
  
• 为了和暴力方法区分，我们不希望直接把主串的指针移到下一个位置开始遍历，而是一直向前方移动，这需要我们移动指针到仍然有可能重新匹配的地方，如何寻找？利用next数组和[0,i-1]的内容的已知信息
• [0,i-1]中的前后缀长度是next[i-1]，而主串匹配子串最基本的要求就是从第一个字符相等。现在主串的头需要移动（因为0作为起点不行了），我们又不像只移动一个，这时可以想到主串的后缀恰好等于子串的开头，举个例子
• 主串是ABCABDC，子串是ABCABC，i此时是5，我们已知[0,4]的ABCAB相等和next[4]=2。主串把0当起点时找不到匹配的，但此时主串[0,4]的末尾和子串的开头相等，都是AB，所以把主串的起点移动到i-next[i-1]=5-2=3后，主串和子串又有了next[i-1]长度的相等段（因为next数组的定义，0-3之间不可能有另外等于子串开头的部分，前后缀一定会覆盖到第一个可能的起点处，如ABACAB匹配ABACAD时，不可能把起点移到中间的A，因为下一位是C，前后缀在计算时就比较过了）
• 这样等价于主串不动，还是从第i位开始比较，而子串从则回退到next[i-1]位，因为子串的[0,i-1)已知和主串是相等的，回到图中的例子就是：
  
  

这种方法的代码如下：

class Solution:def getNext(self, next, s):for i in range(1, len(s)):len_ = next[i - 1]while len_ != 0 and s[i] != s[len_]: #等于0也是没有，会跳过的len_ = next[len_ - 1]if s[i] == s[len_]: #跳出循环要不是0要不相等next[i] = len_ + 1def strStr(self, haystack: str, needle: str) -> int:next = [0] * len(needle)self.getNext(next, needle)i = 0 #主串指针j = 0 #子串指针for i in range(len(haystack)):while j > 0 and haystack[i] != needle[j]:#不匹配，子串到下一个可能匹配的地方next[j-1]，注意只要j>0要一直找，而不是只试一次j = next[j - 1]if haystack[i] == needle[j]:#字符匹配，指针后移j += 1if j == len(needle):#在主串中找到了子串return i - len(needle) + 1return -1