KMP 算法

奋斗吧

擅长邻域：未填写

标签： KMP 算法 Python博客 51CTO博客

2023-05-15 18:24:06 192浏览

KMP 算法，KMP

文章目录

KMP 算法

朴素模式匹配 BF
最长相等前后缀 Lp
next 数组

KMP 算法的时间复杂度
计算 next 数组

[1392. 最长快乐前缀](https://leetcode.cn/problems/longest-happy-prefix/)
[28. 找出字符串中第一个匹配项的下标](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/)
[459. 重复的子字符串](https://leetcode.cn/problems/repeated-substring-pattern/)
[1668. 最大重复子字符串](https://leetcode.cn/problems/maximum-repeating-substring/)
[1764. 通过连接另一个数组的子数组得到一个数组](https://leetcode.cn/problems/form-array-by-concatenating-subarrays-of-another-array/)

KMP 算法

KMP算法易懂版最浅显易懂的 KMP 算法讲解帮你把KMP算法学个通透！（理论篇）求next数组代码篇

KMP 算法，由 Knuth、Morris 和 Pratt 三人于 1977 年联合发表。
KMP 算法的核心为 前缀函数，记作 π(i)，其定义如下：
对于长度为 m 的字符串 s，其前缀函数 π(i)(0 ≤ i < m) 表示 s 的子串 s[0:i] 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 π(i) = 0。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

字符串 aabaaab 的前缀函数值依次为 0,1,0,1,2,2,3。

KMP 是一种字符串模式匹配算法，在字符串（主串）中的模式串定位。

朴素模式匹配 BF

主串 s 和模式 p 从头开始匹配，失配后，s 回溯到开始的下一个字符，p 回溯到开头重新开始匹配，重复操作。
也可以理解为开始 s 和 p 对齐进行匹配，失配后，p 右移一个字符重新开始匹配，重复操作直到结束。

KMP 算法_数据结构

def BF(s, p):
    i = j = 0
    m, n = len(s), len(p)
    while i < m and j < n:        
        if s[i] == p[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0
    if j == n: return i - j
    else: return -1

s = "abcabeabcabcmn"
p = "abcabcmn"
BF(s, p)

最长相等前后缀 Lp

最长相等前后缀：Longest equal prefix，记作 Lp。
除去自身，因为字符串本身前后缀相同。

p = "abcdab"
Lp = "ab"

next 数组

每一个字符前的字符串都有 Lp，next 数组存储子串的 Lp 的长度。

next[i] = j，含义是：下标为 i 的字符前 的字符串 Lp 的长度为 j。

注意：此处定义是把 前缀函数 π(i)的值 右移一位。

p = “abcabcmn”

next = [-1, 0, 0, 0, 1, 2, 3, 0 ] # -1 ‘a’ 前面没有字符串

KMP 算法_bc_02

例如：

KMP 算法_字符串_03

s = "abcabeabcabcmn"
p = "abcabcmn"
i = j = 0 # s, p 的指针
for i < len(s) and j < len(p):
	if s[i] != p[j]: # i = 5 失配
		j = next[j] # j 回退到 next[5] 即 2 的位置
	else: 
		i += 1; j += 1

KMP 算法_字符串_04

p 中的 Lp (前缀) 只有和 s 中的 Lp (后缀) 对齐才有可能匹配成功。
p 中下标 5 前子串是 “abcab”，Lp = “ab”, next[5] = 2 即 Lp 的长度，也是 Lp (前缀) 后的第一个位置（索引从 0 开始），也是失配后 p 需要和 s 当前位置匹配的位置，即指针 j 回退的位置。

next 数组作用有两个：

next[i] 的值表示下标为 i 的字符前的字符串最长相等前后缀的长度；
表示该处字符不匹配时应该回溯到的字符的下标。

KMP 算法的时间复杂度

KMP 算法中多了一个求数组的过程，多消耗了一点点空间。设主串 s 长度为 n, 模式串 p 的长度为 m。求 next 数组时间复杂度为 O(m)，因后面匹配中主串不回溯，比较次数可记为 n，所以 KMP 算法的总时间复杂度为 O(m + n)，空间复杂度记为 O(m)。相比于朴素的模式匹配时间复杂度 O(m * n)。

计算 next 数组

def getnext(p):
    i, j, n = 0, -1, len(p) # i 后缀末尾位置，j 前缀末尾位置 和 最长长度
    nxt = [-1] # 第一个前没有子串
    while i < n - 1:
        if j == -1 or p[i] == p[j]: 
            i += 1
            j += 1
            nxt.append(j)
        else: j = nxt[j] 
    return nxt
p = "abaabcac"
getnext(p)

def KMP(s, p): 
    nxt = getnext(p)
    i = j = 0  # i, j 分别是 s, p 的指针
    m, n = len(s), len(p)
    while i < m and j < n:
        if j == -1 or s[i] == p[j]:
            i += 1
            j += 1
        else: j = nxt[j] # 指针回退
    if j == n: return i - j # 匹配成功
    else: return -1
    
s = "aabaabaaf"
p = "aabaafx"
KMP(s, p)

1392. 最长快乐前缀

『字符串哈希、KMP 』掌握模板，快乐其实很简单

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

class Solution:
    def strStr(self, s: str, p: str) -> int:
    	# 方法一：BF
        n, m = len(s), len(p)
        # 回溯
        i = j = 0
        while i < n and j < m:
            if s[i] == p[j]:
                i += 1
                j += 1
            else:
                i = i - j + 1 # 回溯到下一个
                j = 0
        if j == m: return i - j
        else: return -1        
        # 右移
        for i in range(n - m + 1):
            for j in range(m):
                if s[i + j] != p[j]: break             
            else: return i           
        return -1
        
        # 方法二：KMP
        def getnext(p):
            j, n = 0, len(p)
            nxt = [0] * n
            for i in range(1, n):
                while j > 0 and p[i] != p[j]:
                    j = nxt[j - 1]
                if p[i] == p[j]: j += 1
                nxt[i] = j
            return nxt

        nxt = getnext(p)
        n, m, j = len(s), len(p), 0
        for i in range(n):
            while j > 0 and s[i] != p[j]:
                j = nxt[j - 1]
            if s[i] == p[j]: j += 1
            if j == m: return i - j + 1        
        return -1

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s = haystack.toCharArray(), p = needle.toCharArray();
        int[] next = getNext(p);
        int n = s.length, m = p.length;
        for(int i = 0, j = 0; i < n; i++) {
            while(j > 0 && s[i] != p[j]) 
                j = next[j - 1];
            if(s[i] == p[j]) j++;
            if(j == m) return i - j + 1;
        }
        return -1;
    }
    private int[] getNext(char[] s) {
        int j = 0, n = s.length;
        int[] next = new int[n];
        for(int i = 1; i < n; i++){
            while(j > 0 && s[i] != s[j])
                j = next[j - 1];
            if(s[i] == s[j]) j++;
            next[i] = j;
        }
        return next;
    }
}

459. 重复的子字符串

KMP 算法

KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度；

学习 KMP 算法时，一定要理解其本质。如果放弃阅读晦涩难懂的材料（即使大部分讲解 KMP 算法的材料都包含大量的图，但图毕竟只能描述特殊而非一般情况）而是直接去阅读代码，是永远无法学会 KMP 算法的。读者甚至无法理解 KMP 算法关键代码中的任意一行。

由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。这里留了三个思考题，读者可以在学习完毕后尝试回答这三个问题，检验自己的学习成果：

设查询串的的长度为 n，模式串的长度为 m，需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？

如果有多个查询串，平均长度为 n，数量为 k，那么总时间复杂度是多少？

在 KMP 算法中，对于模式串，需要预处理出一个 fail 数组（next 数组、π 数组）。这个数组到底表示了什么？

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        def kmp(query: str, pattern: str) -> bool:
            n, m = len(query), len(pattern)
            fail = [-1] * m
            for i in range(1, m):
                j = fail[i - 1]
                while j != -1 and pattern[j + 1] != pattern[i]:
                    j = fail[j]
                if pattern[j + 1] == pattern[i]:
                    fail[i] = j + 1
            match = -1
            for i in range(1, n - 1):
                while match != -1 and pattern[match + 1] != query[i]:
                    match = fail[match]
                if pattern[match + 1] == query[i]:
                    match += 1
                    if match == m - 1:
                        return True
            return False
        
        return kmp(s + s, s)

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        def kmp(pattern: str) -> bool:
            n = len(pattern)
            fail = [-1] * n
            for i in range(1, n):
                j = fail[i - 1]
                while j != -1 and pattern[j + 1] != pattern[i]:
                    j = fail[j]
                if pattern[j + 1] == pattern[i]:
                    fail[i] = j + 1
            return fail[n - 1] != -1 and n % (n - fail[n - 1] - 1) == 0
        
        return kmp(s)