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

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

引用

CSDN

1.

https://m.blog.csdn.net/m0_53632564/article/details/145783773

KMP算法是字符串匹配领域的重要算法，其核心思想是通过预处理模式串（子串）来避免不必要的字符比较，从而提高匹配效率。本文将从最长公共前后缀next数组、合并主子串、子串偏移法三个方面深入解析KMP算法的原理和实现。

最长公共前后缀next

这个概念是一个巧妙的技巧，帮助我们在遍历数组时记录其相似特性。虽然这个想法非常巧妙，但其背后的逻辑确实不容易理解。

前缀和后缀定义

• 前缀：不包含最后一个字符的所有以第一个字符开头的连续子串。
• 后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串。

例如，对于字符串 "ababc"：

• 前缀有： "a"、"ab"、"aba"、"abab"
• 后缀有： "c"、"bc"、"abc"、"babc"

最长公共前后缀

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

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

next数组计算

next数组用于记录每个位置的最长公共前后缀的长度。例如，对于模式串 "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数组，方法如下：

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_ + 1

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;
    }
}

合并主子串

这个问题要求在haystack字符串中找出needle字符串的第一个匹配项的下标。如果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 case
            return 0
        s = 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_ + 1
                if next[i] == m:#返回第一个
                    return i - m*2 #合并串从第m+1位开始才是主串，所以主串中开始匹配的下标是i - (m+1) - m + 1=i-2*m
        return -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_ + 1
    def 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 += 1
            if j == len(needle):#在主串中找到了子串
                return i - len(needle) + 1
        return -1