史上最详细的KMP算法教程，看这一篇就够了

🧑‍💻 文章作者：Iareges
🔗 博客主页：https://blog.csdn.net/raelum
⚠️ 转载请注明出处

⚠️ 本文讨论的下标均从 $0$ 开始。

字符串匹配又称模式匹配（pattern matching）。该问题可以概括为「给定字符串 $s$ 和 $t$，在主串 $s$ 中寻找子串 $t$」。字符串 $t$ 称为模式串 (pattern)。模式匹配成功是指在 $s$ 中找到了 $t$（可能存在多个），不成功是指 $s$ 中不存在 $t$。

模式匹配的算法有很多种，这里主要讨论BF算法和KMP算法。

一、BF算法

BF（Brute-Force）算法为暴力解法。设主串 $s=s_0{s}_1\cdots s_{n-1}$，模式串 $t=t_0{t}_1\cdots t_{m-1}$，分别用 $i,j$ 遍历 $s$ 和 $t$（初始均为 $0$），其基本过程如下：

• 第一趟匹配：$i=0,j=0$，从 $s_0,t_0$ 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 $t$ 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第一趟匹配失败；
• 第二趟匹配：$i=1,j=0$，从 $s_1,t_0$ 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 $t$ 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第二趟匹配失败；
• 以此类推，只要有一趟匹配成功，就说明 $t$ 是 $s$ 的子串，返回 $t$ 在 $s$ 中的起始下标。如果 $i$ 超界都没有匹配成功，说明 $t$ 不是 $s$ 的子串，返回 $-1$。

BF算法的实现如下：

int bf(const string &s, const string &t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) i++, j++;
        else i = i - j + 1, j = 0;
    }
    if (j == t.size()) return i - j;
    else return -1;
}

BF算法的动画演示：

BF算法采用了穷举的思路，所以效率不高。该算法在最好的情况下时间复杂度为 $O(m)$，即主串的前 $m$ 个字符正好等于模式串的 $m$ 个字符。在最坏情况下的时间复杂度和平均时间复杂度均为 $O(nm)$。空间复杂度为 $O(1)$。

二、KMP算法

KMP（Knuth-Morris-Pratt）算法比BF算法有较大的改进，主要是消除了主串指针（即 $i$）的回溯，从而提高了匹配效率。

在讲解KMP之前，需要给出一些预备知识。

2.1 字符串基础

子串： 字符串 $s$ 的子串 ，$s[i..j]$，$i\le j$，表示 $s$ 串中从 $i$ 到 $j$ 这一段，也就是顺次排列 $s[i],s[i+1],\cdots ,s[j]$ 形成的字符串。有时也会用 $s[i..j]$，$i>j$ 来表示空串。

子序列： 字符串 $s$ 的子序列是从 $s$ 中将若干元素提取出来并不改变相对位置形成的序列，即 $s[p_1],s[p_2],\cdots ,s[p_k]$，$0\le p_1<p_2<\cdots <p_k\le |s|-1$。

后缀： 是指从某个位置 $i$ 开始到整个串末尾结束的一个特殊子串。字符串 $s$ 的从 $i$ 开头的后缀表示为 $s[i..|s|-1]$。

真后缀： 指除了 $s$ 本身的 $s$ 的后缀。

前缀： 是指从串首开始到某个位置 $i$ 结束的一个特殊子串。字符串 $s$ 的以 $i$ 结尾的前缀表示为 $s[\mathrm{0..}i]$。

真前缀： 指除了 $s$ 本身的 $s$ 的前缀。

📝 其他一些地方定义的前后缀就是这里的真前后缀。

例如，对于字符串 ababab，其真前缀有 a，ab，aba，abab，ababa，真后缀有 b，ab，bab，abab，babab。公共（相等）的真前后缀有 ab，abab，最长公共真前后缀为 abab。再例如，对于字符串 aaaabaaaaa，最长公共真前后缀为 aaaa。

2.2 next数组

为方便接下来的叙述，我们先来做一个简化。

回顾1.1节，BF算法的实现中设置了两个指针：$i,j$，但在BF算法的动画演示中，我们可以只考虑主串的指针 $i$，这是因为模式串每次都向右移动一位并与主串「网格对齐」，所以只需要比较 $i$ 所指向的两个（对齐）网格中的元素，如下图所示：

因为我们无法在代码中实现「模式串向右移动」这种操作，所以代码实现必须要用两个指针。但是在动画演示中，模式串可以向右移动，所以我们只需要主串的指针就足够了。接下来的讨论都将基于一个指针。

设主串的长度为 $n$，模式串的长度为 $m$，先来看如何用一个指针描述BF算法（即从数学的角度描述1.1节中的动画）。初始时，$i=0$，模式串与主串左对齐。比较 $i$ 指向的两个网格中的元素，如果相等，则让 $i$ 先右移一位，然后继续比较（前提是可以比较）；如果不等，则让模式串先右移一位，然后“回溯” $i$，即置 $i:=i-m+2$，然后继续比较（这里回溯之所以加双引号是因为如果 $m=1,2$，则 $i$ 不会后退，但绝大多数情况下都认为 $m>2$）。若 $i=模式串向右移动的总距离+m$，则意味着匹配成功，如下图所示：

BF算法效率低下的一大原因就是指针 $i$ 会后退，而KMP的指针 $i$ 只前进不后退，那如何做到不后退呢？

不妨假设在 $i$ 处失配，即：

如果是BF算法，此时的做法是先将模式串向右移动一位，然后回溯 $i$，而在KMP算法中，$i$ 不能后退，因此我们只能先右移模式串，然后再右移 $i$。问题来了，模式串应当右移多少位呢？

不论右移多少位，在移动之后，我们至少要保证 $i$ 左侧（不包括 $i$）的元素能够一一匹配，如下图所示：

在模式串向右移动后，检查 $i$ 处的两个元素是否匹配，若是，则让 $i$ 继续向右移动，否则，继续右移模式串。

容易看出，蓝框中的部分均相同。为方便叙述，这里换回双指针进行讨论，其中主串的指针为 $i$，模式串的指针为 $j$。事实上，可以证明模式串向右移动等价于 $j$ 后退，而 $j$ 的更新值正是：模式串位于 $j$ 左侧（不包括 $j$）的子串的最长公共真前后缀的长度，记为 $next[j]$。

根据上图，我们还能得到一个公式：

$$模式串向右移动的距离=j-j的更新值=j-next[j]$$

📝 可能会有读者好奇，模式串一下子右移这么多，就不怕移动的过程中间丢掉一些匹配的情况吗？这里可以采用反证法，假设在中间有匹配的情况存在，那么模式串向右移动的距离就要比原先的少，从而 $next[j]$ 的值就要比原先的大，而原先 $next[j]$ 的定义就是「最长公共真前后缀的长度」，与「最长」矛盾，故中间不可能有匹配的情况存在。

如果公共真前后缀根本就不存在，我们就需要将模式串不断右移直至模式串的第一个元素与指针 $i$ 所指向的元素对齐，这相当于让模式串右移 $j$ 位，从而可知此时 $next[j]=0$。

读到这里，相信你已经发现，$next$ 数组只与模式串有关，且长度和模式串的长度相同。设模式串为 $t$，$next$ 数组的完整定义如下：

n e x t [ i ] = { − 1 , i = 0 max ⁡ 0 < k < i { k : t [ 0.. k − 1 ] = t [ i − k . . i − 1 ] } , 公共真前后缀集合非空 0 , 其他 next[i]= \begin{cases} -1,&i=0\\ \max\limits_{0<k<i}\{k:t[0..k-1]=t[i-k..i-1]\},&公共真前后缀集合非空 \\ 0,&其他 \end{cases} next[i]=⎩ ⎨ ⎧​−1,0<k<imax​{k:t[0..k−1]=t[i−k..i−1]},0,​i=0公共真前后缀集合非空其他​

可以发现，一定有 $next[1]=0$，至于为什么定义 $next[0]=-1$ 下文会提及。

2.3 KMP的实现

先不讨论 $next$ 数组是如何生成的，假设我们已经拥有了 $next$ 数组，接下来利用该数组实现KMP算法。

⚠️ 我们使用 nxt 代替 $next$ 防止不必要的冲突。

每次比较时，若 $s[i]$ 与 $t[j]$ 相等，则执行 i++, j++ 并继续比较；若不等，则执行 j = nxt[j] 以更新 $j$（相当于向右移动模式串）。一个特殊情况是，如果某一次比较出现了 $s[i]$ 不等于 $t[0]$，即在模式串的第一个字符处失配，则 $j$ 的更新值为 j = nxt[0] = -1，接下来应当执行 i++, j++，相当于让模式串右移一位并重新在模式串的第一个字符处进行比较。由此可见，定义 $next[0]=-1$ 的作用是将两种情况合并为一种情况并达到简化代码的目的。

KMP算法的实现如下：

int kmp(const string &s, const string &t) {
    int i = 0, j = 0;
    while (i < s.size() && j < (int) t.size()) {  // 因为j可能是-1，所以这里需要强制类型转换，否则当j为-1时会跳出循环
        if (j == -1 || s[i] == t[j]) i++, j++;
        else j = nxt[j];
    }
    if (j == t.size()) return i - j;
    else return -1;
}

2.4 next数组的生成

首先一定有 $next[0]=-1,next[1]=0$。不妨假设我们已经求出了 $next[i]=k$，下面来求 $next[i+1]$。

因为 $next[i]=k$，故 $t[\mathrm{0..}k-1]=t[i-k..i-1]$，下面分两种情况讨论：

• 情况一：$t[k]=t[i]$。此时有 $t[\mathrm{0..}k]=t[i-k..i]$，所以应有 $next[i+1]=k+1$。会不会还存在 $t[\mathrm{0..}k+1]=t[i-k-\mathrm{1..}i]$ 这种情况使得 $next[i+1]=k+2$ 呢？若存在，则可推得 $t[\mathrm{0..}k]=t[i-k-\mathrm{1..}i-1]$，这说明 $next[i]=k+1$，与 $next[i]=k$ 矛盾。
• 情况二：$t[k]\ne t[i]$。记 $k_1\triangleq next[k]$，于是有 $t[\mathrm{0..}{k}_1-1]=t[k-k_1..k-1]$，又因 $t[\mathrm{0..}k-1]=t[i-k..i-1]$，故有 $t[\mathrm{0..}{k}_1-1]=t[k-k_1..k-1]=t[i-k..i-k+k_1-1]=t[i-k_1..i-1]$，即 $t[\mathrm{0..}{k}_1-1]=t[i-k_1..i-1]$。若 $t[k_1]=t[i]$，则根据情况一，$next[i+1]=k_1+1$；若 $t[k_1]\ne t[i]$，则记 $k_2\triangleq next[k_1]$，重复执行情况二的操作。若在某一步发现 $k_n=-1$，说明已经回退到了 $t$ 的开头，此时应置 $next[i+1]=0$。

求解 $next$ 数组的算法如下：

void getNext(int nxt[], const string &t) {
    int i = 0, k = -1;
    nxt[0] = -1;
    while (i < t.size() - 1) {
        if (k == -1 || t[k] == t[i]) nxt[++i] = ++k;
        else k = nxt[k];
    }
}

KMP算法的完整实现：

#include <iostream>
#include <string>

using namespace std;

const int N = 1e5 + 10;

int nxt[N];

int kmp(const string &s, const string &t) {
    int i = 0, j = 0, k = -1;
    nxt[0] = -1;
    while (i < t.size() - 1) {
        if (k == -1 || t[k] == t[i]) nxt[++i] = ++k;
        else k = nxt[k];
    }

    i = 0;
    while (i < s.size() && j < (int) t.size()) {
        if (j == -1 || s[i] == t[j]) i++, j++;
        else j = nxt[j];
    }

    if (j == t.size()) return i - j;
    else return -1;
}

int main() {
    string s, t;
    cin >> s >> t;
    cout << kmp(s, t) << endl;
    return 0;
}

KMP算法的最好时间复杂度为 $O(m)$，平均时间复杂度为 $O(n+m)$，最坏时间复杂度仍为 $O(nm)$。空间复杂度为 $O(m)$。

三、改进的KMP算法

之前我们定义的 $next$ 数组在某些情况下仍然存在缺陷。这里换回单指针进行讨论。

在下面的例子中，失配处为 $i=3$：

于是模式串应当向右移动 $3-next[3]=1$ 位，很显然移动之后依然是失配的，此时模式串应当向右移动 $2-next[2]=1$ 位，如此进行下去，可以发现，模式串要执行 $4$ 次「右移一位」这样的操作才能够开始新一轮的匹配。

根据 $next$ 数组的定义，模式串做了很多的无用功，而按照人类思维，第一次失配时就应该让模式串一次性右移 $4$ 位。

3.1 nextval数组

上述问题可以通过改进 $next$ 数组得到解决，将 $next$ 数组改为 $nextval$ 数组。与 $next[0]$ 一样，先置 $nextval[0]=-1$。

这里换回双指针进行讨论，假设在 $s[i],t[j]$ 处失配，下一步我们会求 $j$ 的更新值 $next[j]$，不妨设为 $k$。

已知 $s[i]\ne t[j]$，接下来分两种情况讨论：

• 如果 $t[k]=t[j]$，则有 $s[i]\ne t[k]$，即更新 $j$ 后再匹配时必然会失配。为防止这种无用功，我们可以直接令 $nextval[j]=nextval[k]$，即取 $j$ 的更新值为 $k$ 的更新值。
• 如果 $t[k]\ne t[j]$，则更新 $j$ 后再匹配时不会失配，所以 $j$ 的更新值不变，即 $nextval[j]=k$。

求解 $nextval$ 数组的算法如下：

void getNextval(int nxtval[], const string &t) {
    int j = 0, k = -1;
    nxtval[0] = -1;
    while (j < t.size() - 1) {
        if (k == -1 || t[k] == t[j]) {
            if (t[++k] != t[++j]) nxtval[j] = k;
            else nxtval[j] = nxtval[k];
        } else k = nxtval[k];
    }
}

3.2 KMP算法最终版（nextval版）

为了防止 size_t 和 int 类型之间的转化造成不便，这里全部统一成 int 类型。

#include <iostream>
#include <string>

using namespace std;

const int N = 1e5 + 10;

int nxtval[N];

int kmp(const string &s, int s_len, const string &t, int t_len) {
    int i = 0, j = 0, k = -1;
    nxtval[0] = -1;

    while (j < t_len - 1) {
        if (k == -1 || t[k] == t[j]) {
            if (t[++k] != t[++j]) nxtval[j] = k;
            else nxtval[j] = nxtval[k];
        } else k = nxtval[k];
    }

    j = 0;
    while (i < s_len && j < t_len) {
        if (j == -1 || s[i] == t[j]) i++, j++;
        else j = nxtval[j];
    }

    if (j == t_len) return i - j;
    else return -1;
}

int main() {
    string s, t;
    cin >> s >> t;
    int s_len = s.size(), t_len = t.size();
    cout << kmp(s, s_len, t, t_len) << endl;
    return 0;
}

与改进前的KMP算法一样，本算法的平均时间复杂度也是 $O(n+m)$。

四、寻找所有子串的KMP算法（推荐）

如果 $s$ 中含有多个 $t$，则我们之前给出的算法只能返回 $t$ 首次出现的位置的起始下标，不能返回 $t$ 所有出现的位置的起始下标。

为求得 $s$ 中所有的 $t$，这里需要引入前缀函数。

4.1 前缀函数

⚠️ 很多教程都把前缀函数和 $next$ 数组混为一谈，然而这是不严谨的。

前缀函数和 $next$ 数组的定义十分相似。给定一个长度为 $m$ 的模式串 $t$，其前缀函数被定义为一个长度为 $m$ 的数组 $\pi$，$\pi [i]$ 表示 $t[\mathrm{0..}i]$ 这个子串的最长公共真前后缀的长度。

不难发现 $\pi$ 数组与 $next$ 数组之间的关系如下：

$$\pi [i]=\{\begin{array}{ll}next[i+1],& 0\le i\le m-2\\ t的最长公共真前后缀的长度,& i=m-1\end{array}$$

根据 $\pi$ 的定义，一定有 $\pi [0]=next[1]=0$，于是求解 $\pi$ 数组只需要求解 $\pi [\mathrm{1..}m-1]$。

4.2 利用前缀函数实现KMP算法

同样地，我们先不管 $\pi$ 数组是如何生成的，假设我们已经拥有了 $\pi$ 数组，接下来利用它来实现「寻找所有子串的KMP算法」。

设主串 $s$ 的长度为 $n$，模式串 $t$ 的长度为 $m$。考虑构造字符串 $t+\#+s$，其中 $\#$ 为一个既不会出现在 $s$ 中也不会出现在 $t$ 中的分隔符。

设 $\pi$ 是字符串 $t+\#+s$ 所对应的前缀函数，可以发现，$\pi [m-1]$ 就是 $t$ 的最长公共真前后缀的长度，而 $\pi [m]$ 一定为 $0$，这是因为 $t$ 中不含有 $\#$，所以不可能找到公共的真前后缀，

下面考虑 $\pi [i](i>m)$ 的值。由于 $\#$ 的存在，易知

$$\pi [i]\le m,i>m$$

当 $\pi [i]=m$ 时，意味着 $t$ 完整出现在该位置，并且右端点位于 $i$ 处。 此时 $t$ 在 $s$ 中的起始下标为 $i-(m-1)-(m+1)=i-2m$。于是我们只需要遍历 $\pi$ 数组即可求得 $t$ 的所有起始下标：

vector<int> kmp(const string &s, const string &t) {
    string cur = t + '#' + s;
    int n = s.size(), m = t.size();
    vector<int> res;
    vector<int> pi = getPrefix(cur);
    for (int i = m + 1; i <= n + m; i++)
        if (pi[i] == m) res.push_back(i - 2 * m);
    return res;
}

4.3 π \pi π 数组的生成

注意到 $next$ 数组是由 $\pi$ 数组平移得来，所以我们可以采用类似于求解 $next$ 数组的思路来求解 $\pi$ 数组，但这里我们采用全新的解法（思路依然不变）。

假设已经求出了 $\pi [i-1]=k$，下面来看如何求 $\pi [i]$。

已知 $t[\mathrm{0..}k-1]=t[i-k..i-1]$，如果此时有 $t[k]=t[i]$，那么可得 $\pi [i]=k+1$。如果 $t[k]\ne t[i]$，记 $k_1\triangleq \pi [k-1]$，于是有 $t[\mathrm{0..}{k}_1-1]=t[k-k_1..k-1]=t[i-k..i-k+k_1-1]=t[i-k_1..i-1]$，即 $t[\mathrm{0..}{k}_1-1]=t[i-k_1..i-1]$，如果此时 $t[k_1]=t[i]$，那么 $\pi [i]=k_1+1$，否则记 $k_2\triangleq \pi [k_1-1]$，重复执行上述操作。

若在某一步出现了 $k_n=0$，说明已经回退到了 $t$ 的开头，此时应置 $\pi [i]=0$。

vector<int> getPrefix(const string &t) {
    int m = t.size();
    vector<int> pi(m);
    for (int i = 1; i < m; i++) {
        int k = pi[i - 1];
        while (k && t[k] != t[i]) k = pi[k - 1];
        if (t[k] == t[i]) k++;
        pi[i] = k;
    }
    return pi;
}

4.4 KMP算法最终版（前缀函数版）

考虑到用 vector 存储 $\pi$ 数组效率低下，这里改用原生数组。

不妨假设 $n$ 的数量级为 $10^6$，$m$ 的数量级为 $10^5$。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int N = 1e6 + 1e5 + 10;

int pi[N];

vector<int> kmp(const string &s, const string &t) {
    int n = s.size(), m = t.size();
    string r = t + '#' + s;

    for (int i = 1; i <= n + m; i++) {
        int k = pi[i - 1];
        while (k && r[k] != r[i]) k = pi[k - 1];
        if (r[k] == r[i]) k++;
        pi[i] = k;
    }

    vector<int> res;
    for (int i = m + 1; i <= n + m; i++)
        if (pi[i] == m) res.push_back(i - 2 * m);
    return res;
}

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> res = kmp(s, t);
    for (auto &i: res) cout << i << ' ';
    return 0;
}

References

[1] https://blog.csdn.net/yyzsir/article/details/89462339
[2] 数据结构教程（Python语言描述）
[3] https://oi-wiki.org/string/basic/
[4] https://www.bilibili.com/video/BV1AY4y157yL
[5] https://oi-wiki.org/string/kmp/文章来源地址https://www.toymoban.com/news/detail-843900.html

到了这里，关于史上最详细的KMP算法教程，看这一篇就够了的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！