当老师讲到字符串的时候，必然会介绍字符串的匹配算法，我的老师也是。

但同我的老师一样，大多老师都只会介绍Brute-Force算法（暴力算法），需要O(nm)的时间复杂度。

然而，真的就没有更好的算法了吗？

那必然不可能。我们这次就来聊聊这个精妙的字符串匹配算法——KMP算法。

串

想必能点开这篇笔记的朋友都对串很熟悉了吧…

如果不熟悉的话建议以后再回过头来看，KMP较难理解，不适合初学者。

串匹配

问题描述

给出一个主串（str）与一个模式串（pattern），编写一段程序找出模式串在主串中第一次出现的位置，若未能找到，返回-1。

例：主串为"aaaaa123333451234hhahan"，模式串为"1234"。观察到主串的第14位开始能与模式串匹配：“aaaaa123333451234hhahan”，返回13（数组下标从0开始，所以13对应第14位）。

问题分析（Brute-Force）

很显然，以一般人的思维都能想到，让程序像人脑一样进行逐位对比。先将模式串与主串对齐：

发现匹配失败，便将模式串后移，继续匹配：

很显然，还是匹配失败，于是重复上述过程，直到重复到第14次：

匹配成功，返回13。

这么看来，这个算法貌似没什么问题。

是的，没有一点问题，的确能正常的运行。但是效率极其低下。想象一下，如果是一个长度9999主串，和一个长度为888的匹配串，这个匹配串又恰好出现在主串的末尾。那我们光是移动匹配串就需要九千多次，再加之计算机进行逐位对比时还要遍历一遍这个888位的匹配串，需要的匹配次数可是百万级别的，那如果更长的串呢？

时间复杂度为O(nm)的BF算法自然不能满足我们，于是，更加优秀的算法就应运而生。

KMP算法

实现思路

KMP算法是由D.E.Knuth，J.H.Morris和V.R.Pratt三位大佬共同提出的算法，因此取他们的名字称为Knuth-Morris-Pratt算法。可以实现时间复杂度为O(n+m)的字符串匹配，比起BF的O(nm)，有了显著提升。

我们先来从一道串匹配开始吧：

先将模式串对应主串开头，逐位对比，当对比到第5位的时候，发现匹配失败，于是我们就将指针 i 回退到主串的第二位，将指针 j 回退到模式串的第1位，重复匹配过程。

（注意：模式串在内存中实际不会移动，我们所说的一切移动都是指针 i 和 j 的移动，图中串的偏移只是为了读者阅读方便）

这时，我们发现，i 指向的b与 j 指向的a不匹配，从一开始就不匹配，可以直接跳过，进入下一次。依此类推……

匹配的过程中，你会发现，模式串中这段“ab”的部分是重复的，我们在第一次匹配的时候其实就已经在主串中找到“ab”的位置了，那能不能把这个特性利用起来，不用重复地匹配“ab”呢？

再让我们回到第一次匹配失败的时候：

既然模式串中开头的“ab”只有在主串的第3位才能正确匹配，我们就不用考虑 i 从2开始的情况了，转而直接让 i 对准第三位，j 对准第1位。这时 i 对准的第三位和下一位分别为“ab”，j 对准的第一位和下一位也分别为“ab”，所以我们也不用考虑了。i 完全可以停留在上次匹配失败的位置，转而让 j 回退到第三位，即第一个“ab”后的那一位。

好了，我们已经发现了，在匹配失败的时候，主串中的 i 指针实际上不需要回退，只需要模式串的 j 指针回退，且不必回退到起点，只需回退到某个点。那我们只需要计算出每一位所要回退到哪个点，不就可以实现KMP算法了吗？

在介绍如何算出这个点之前，我先来介绍两个概念。

前缀与后缀

对于任意一个串X，总存在字符串A和B，使得AS=X，SB=X。其中A被称为前缀，B被称为后缀，S为任意元素。

说简单点，前缀就是开头的一段字串，后缀就是结尾的一段字串。

我们所要找的“重复部分”，就是前缀集合与后缀集合的交集中的最长元素。

比如：对于字符串“ababa”：

前缀集合={“a”，“ab”，“aba”，“abab”}；

后缀集合={“a”，“ba”，“aba”，“baba”}；

它们的交集={“a”，“aba”}；

由于“aba”的长度大于“a”，所以“aba”就是我们要找的重复部分

所以，假如把“ababac”作为模式串，与主串“ababaxxxx”在 j 指向第六位的时候匹配失败了。那这时我们要退到哪一位呢？

观察第六位以前的部分“ababa”，算出重复部分长度为3，也就是说前三位与 i 指针前面的三位可以完美匹配，那就只要把 j 退到第四位就可以了。

（至于为什么我们知道主串中 i 前面的三位能和模式串的前三位匹配。因为 i 前面的三位已经和 j 前面的三位匹配过了，而 j 前面的三位又和模式串的开头三位重复，当然可以完美匹配啦。）

如果这个逻辑没捋清楚的话麻烦多读几遍，或者找找其他教程。毕竟这是这个算法的核心部分。

好啦，那对于模式串中的每一位，我们只要计算出这一位前面的那部分的前缀集合与后缀集合的交集中的最长元素的长度，就可以实现正确的回退了。我们用一个名为PMT(Partial Match Table)的数组来存储这些信心，只要有了PMT，就能够实现KMP算法了。

代码实现

KMP

我们先来看KMP的部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int KMP(string str, string pattern)
{
    vector<int> pmt = PMT(pattern);
    for (string::size_type i = 0, j = 0; i < str.size(); i++) //i在主串移动, j在模式串移动
    {
        while (j > 0 && str[i] != pattern[j]) //匹配失败, 将模式串光标移到pmt数组的前一位记录的位置
            j = pmt[j - 1];
        if (str[i] == pattern[j]) //匹配成功, 光标后移, 检查下一位
            j++;
        if (j == pattern.size()) //j走到模式串结尾, 说明匹配成功
            return i - j + 1;
    }
    return -1; //能走到这里说明匹配失败
}

这里解释一个细节：

  • 为什么匹配失败的时候要回到pmt记录的前一位的位置？

    其实有的人喜欢把pmt数组的所有元素都后移一位，记录为next数组，这样就可以不用回到前一位了。两种方法都行，我记录标准的pmt数组完全是个人喜好，毕竟pmt记录的是 j 指针所对应的那一位以前的部分，所以数值也就退一位正好对应了。其实是没有差别的。

    如果暂时还是没法很好地理解pmt数组的话，可以看张图，动动笔，一一对应一下。

看得出来，这部分算法的时间复杂度为O(n)，接下来只要把pmt数组求出来就可以了。

PMT

那么pmt数组要怎么求呢？可能最容易想到的就是暴力用O(m²)的算法求了……虽然也不是不行，但如果都走到这一步了还要用那种低效率的办法，还不如一开始就直接用Brute-Force来匹配呢哈哈哈。

聪明的你可能已经发现了，求pmt的过程本身就是一个串匹配的过程。

我们只要对每个子串，分别对其本身使用KMP算法就行了呀。不过，得让 i 从第二位开始，不然不就一定能匹配到了嘛！

或许看到这里你会迷惑，那这个算法的pmt数组要怎么得到呢？可以自己模拟试试看，会发现每一次匹配所需的值，都已经在上一轮匹配就记录在pmt中了。

具体过程我们用几张图来大概模拟一下：

首先pmt的第一位我们记为0（ pmt[0] = 0 ），毕竟刚开始无法匹配。

发现第一位无法匹配，将 i 后移，pmt[1] = j = 0；接着开始下一轮：

发现匹配成功，那么pmt[2] = j+1 = 1；接下来接着重复这个过程。

这时发现匹配失败了，那 j 指针就要退回到pmt[j-1]位，即pmt[2] = 1。

然而还是匹配失败，所以继续回退到 j = 0，同时数组该为置零。同时 i 已经走到结尾，pmt数组也被完整求出来了。

以下为代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> PMT(string pattern)
{
    vector<int> pmt((int)pattern.size(), 0);
    int j = 0;
    for (string::size_type i = 1; i < pattern.size(); i++)
    {
        while (j > 0 && pattern[i] != pattern[j]) //匹配失败, 像KMP算法一样将光标移到pmt[j-1]位
            j = pmt[j - 1];
        if (pattern[i] == pattern[j]) //匹配成功, 光标后移, 记录pmt
            j++;
        pmt[i] = j; //将数组第i位记录为j的值
    }
    return pmt;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

vector<int> PMT(string pattern)
{
    vector<int> pmt((int)pattern.size(), 0);
    int j = 0;
    for (string::size_type i = 1; i < pattern.size(); i++)
    {
        while (j > 0 && pattern[i] != pattern[j]) //匹配失败, 像KMP算法一样将光标移到pmt[j-1]位
            j = pmt[j - 1];
        if (pattern[i] == pattern[j]) //匹配成功, 光标后移, 记录pmt
            j++;
        pmt[i] = j; //将数组第i位记录为j的值
    }
    return pmt;
}

int KMP(string str, string pattern)
{
    vector<int> pmt = PMT(pattern);
    for (string::size_type i = 0, j = 0; i < str.size(); i++) //i在主串移动, j在模式串移动
    {
        while (j > 0 && str[i] != pattern[j]) //匹配失败, 将模式串光标移到pmt数组的前一位记录的位置
            j = pmt[j - 1];
        if (str[i] == pattern[j]) //匹配成功, 光标后移, 检查下一位
            j++;
        if (j == pattern.size()) //j走到模式串结尾, 说明匹配成功
            return i - j + 1;
    }
    return -1; //能走到这里说明匹配失败
}

int main()
{
    // // DEBUG
    // string s = "ababababcd";
    // string p = "ababcd";
    // cout << KMP(s, p);
    return 0;
}

结

通过以上代码我们可以得出：求解PMT数组的时间复杂度为O(m)，进行KMP的时间复杂度为O(n)，所以该算法的时间复杂度O(n+m)，远远低于BF的O(nm)。

KMP算法虽然好用，但是确实有点难理解，特别是对于我这种算法初学者来说……学的时候起码翻了十几篇教程，五六个视频，才感觉大体体会到了中心思想。所以我这篇笔记或许也存在许多疏漏和需完善的地方。如果能对你有些帮助，那自然是我的荣幸。但如果哪些地方没读懂，也不一定要在我这死磕，毕竟有很多别的大佬写的教程，虽然过程可能没有我叙述得这么细致，但是原理肯定讲得比我清楚，建议移步他们的教程。