问答|KMP算法学习笔记

问题

目录

1. KMP是什么，做什么用的
2. KMP算法的高效体现在哪
3. 如何KMP算法的next数组
4. KMP的代码
5. KMP的时间复杂度是多少

有句话很有趣：Stay hungry, stay foolish. 个人根据对这句话的理解 以一个有强烈求知欲的小白的角度，用提问解答的方式组织全文，以此发现自己知识图谱的不足并积极学习新的知识。

看法

KMP是什么，做什么用的

KMP全称为Knuth Morris Pratt算法，三个单词分别是三个作者的名字。KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置(比如在"hello,world"主串中查找"world"模式串的位置)。

KMP算法的高效体现在哪

高效性是通过和其他字符串搜索算法对比得到的，在这里拿BF(Brute Force)算法做一下对比。BF算法是一种最朴素的暴力搜索算法。它的思想是在主串的[0, n-m]区间内依次截取长度为m的子串，看子串是否和模式串一样(n是主串的长度，m是子串的长度)。代码是这样:

func bf(main, pattern string) int {
    if len(main) == 0 || len(pattern) == 0 || len(main) < len(pattern) {
        return -1 // 异常判断，若不存在返回-1
    }
    n, m := len(main), len(pattern)
    for i := 0; i <= n-m; i++ { // 结束条件是n-m,不需要到n
        sub := main[i : i+m] //截出主串中的对比串
        if sub == pattern {
            return i //返回索引值
        }
    }
    return -1 // 主串中不存在模式串
}

BF的时间复杂度是O(NN)，存在很大优化空间。当模式串和主串匹配时，遇到模式串中某个字符不能匹配的情况，对于模式串中已经匹配过的那些字符，如果我们能找到一些规律，将模式串多往后移动几位，而不是像BF算法一样，每次把模式串移动一位，就可以提高算法的效率。比如说在"ababaababacd"中查找"ababac"*，可以避免一些字符之间的比较。

下面通过一个具体的例子来看看可以跳过的情况。比如主模式串是"ababaeaba",模式串是"ababacd",在BF算法中，遇到不匹配的情况是这样处理的:

main:    "ababaeaba" // 例如这两个串，当sub为"ababaea"时和"ababacd"进行对
pattern: "ababacd"   // 比，当main[i]为e时，发现和pattern[j]的值e不一致，BF
                     // 的做法是去下一个sub,即用"babaeab"和pattern进行比较。

我们希望找到一些规律，遇到两个字符不匹配的情况时，希望可以多跳几个字符，减少比较次数。KMP算法的思想是：在模式串和主串匹配过程中，当遇到不匹配的字符时，对于主串和模式串中已对比过相同的前缀字符串，找到长度最长的相等前缀串，从而将模式串一次性滑动多位，并省略一些比较过程。在上个例子，KMP算法中，是这样处理的：

main:    "ababaeaba" // 比如main中的"ababa"子串，对标为[2~4]的"aba"和pattern中下
pattern: "ababacd"   // 标为[0~2]的"aba"相同,此时可以滑动j-k位,即j=j-k。(其中j是
                     // pattern中"c"的下标,k是"abc"的长度)。
            "ababaeaba"          // 比较过程中，main[5]为"e"和pattern[5]为"c"不匹配，但是两个
            "ababacd"            // 串中都有相同的"aba"前缀,所以可以滑动j-k位
                    |           
                    ∨
            "ababaeaba"   
                "ababacd"
                    |               // 滑动j-k位后发现main[5]和patterb[3]不相同，需要再次滑动
                    ∨
            "ababaeaba"   
                    "ababacd" // 滑动过程和上次类似。

通过这个例子可以看出，每次滑动的位数是j-k，滑动位数和主串无关，仅通过模式串就可以求出。在KMP算法中通过next数组来存储当两个字符不相等时模式串应该移动的位数。

如何KMP算法的next数组

再次明确next数组的含义 : next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。 next[i] = j 表示下标以i-j为起点，i为终点的后缀和下标以0为起点，j为终点的前缀相等，且此字符串的长度最长。用符号表示为p[0~j] == p[i-j~i]。下面以"ababacd"模式串为例，给出这个串的next数组。

模式前缀	前缀结尾下标	最长能匹配前缀子串结尾字符的下标	next数组的取值	匹配情况
a	0	-1	next[0] = -1	无
ab	1	-1	next[1] = -1	无
aba	2	0	next[2]=0	pattern[2]==pattern[0]
abab	3	1	next[3]=1	pattern[2:4]==pattern[0:2]
ababa	4	2	next[4]=2	pattern[2:5]==pattern[0:3]
ababac	5	-1	next[5]=-1	无

KMP的代码

下面给出KMP算法的完整代码，里面有详细的注释。注意Go语言版本的代码模式串和主串的下标都是从0开始的，C++版本的代码从1开始，你可以比较一下两种下标代码的区别。

Go

func kmp(s string, pattern string) int {
    n, m := len(s), len(pattern)
    if n < m {
        return -1
    }

    next := make([]int, m)
    // 把next数组中全部初始化为-1
    for index := range next {
        next[index] = -1
    }
    //求next数组中的值
    for i := 1; i < m-1; i++ { // i从1开始,因为第一个字符如果比较失败了,需重新开始匹配 // i取不到m-1的值, 因为取到m-1意味着整个字符串都相等
        j := next[i-1]         // 前i-1的值是之前循环中比较过的,这里j初始化为next[i-1]

        for pattern[j+1] != pattern[i] && j != -1 { // 因为这里是pattern[i]和pattern[j+1]进行比较
            j = next[j]                             // 所以这里j是退回到next[j]的位置再进行循环比较
        }

        if pattern[j+1] == pattern[i] { //因为每次循环只会新增一个字符,所以这里用if判断一个新字母即可.
            j++                         // 如果相等则j++
        }

        next[i] = j // 当前的取值
    }
    // 匹配的过程
    j := 0 //模式串从0下标开始匹配
    for i := 0; i < n; i++ {
        for j > 0 && s[i] != pattern[j] { // j>0意为j没有退回起点 //s[i] != pattern[j]意为两个字符出现不匹配的情况
            j = next[j-1] + 1 // pattern[j]和s[i]不一致,说明前next[j-1]是匹配的,所以移动next[j-1]位;因为s[i]要继续和pattern[j]进行比较,所以j还需加1
        }

        if s[i] == pattern[j] {
            if j == m-1 { //因为j从下标0开始,所以m需减1,两者相等说明循环了len(m)次
                return i - m + 1
            }
            j++ //否则继续判断下一个字符
        }
    }
    return -1
}

C++

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

如果看了注释之后还是对代码有疑问，可以通过下面的测试用例打断点观察代码的运行过程。

func main() {
    a := "ababaababacd"
    b := "ababac"
    fmt.Print(kmp(a, b))
}

KMP的时间复杂度是多少

KMP的时间复杂度是O(n), 证明方法如下。

//1.kmp两个循环类似,分析一个即可
for i := 0; i < n; i++ { //4. 两个循环的时间复杂度是O(2n),所以KMP的时间复杂度是O(n)
        for j > 0 && s[i] != pattern[j] { 
      j = next[j-1] + 1 //3. 这里j会减值,由于next[j-1]肯定小于j,所以j最多减n次
        }

        if s[i] == pattern[j] {
            if j == m-1 { 
                return i - m + 1 
            }
            j++ //2. 在循环中,每次循环j最多+1,所以j最多加n次
        }
    }

---

本文涉及到的算法代码已上传至常见笔试算法-Go语言版本，欢迎读者去点star~

欢迎关注我的公众号: 薯条的自我修养

本公众号有对应读者群，赞赏后可加入。可私信我微信709834997，备注：申请加入薯条公号读者群。