当前位置：首页 > 卖家故事 > 史上最详细的KMP算法教程，看这一篇就够了

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

时间：2024-04-16 08:45:26 来源：网络cs 作者：纳雷武栏目：卖家故事阅读：

标签：教程详细

阅读本书更多章节>>>>

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

一、BF算法二、KMP算法2.1 字符串基础2.2 next数组2.3 KMP的实现2.4 next数组的生成三、改进的KMP算法3.1 nextval数组3.2 KMP算法最终版（nextval版）四、寻找所有子串的KMP算法（推荐）4.1 前缀函数4.2 利用前缀函数实现KMP算法4.3 π \pi π 数组的生成4.4 KMP算法最终版（前缀函数版） References

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

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

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

一、BF算法

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

第一趟匹配： i = 0 , j = 0 i=0,j=0 i=0,j=0，从 s 0 , t 0 s_0,t_0 s0,t0 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 t t t 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第一趟匹配失败；第二趟匹配： i = 1 , j = 0 i=1,j=0 i=1,j=0，从 s 1 , t 0 s_1,t_0 s1,t0 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 t t t 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第二趟匹配失败；以此类推，只要有一趟匹配成功，就说明 t t t 是 s s s 的子串，返回 t t t 在 s s s 中的起始下标。如果 i i i 超界都没有匹配成功，说明 t t t 不是 s s s 的子串，返回 − 1 -1 −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 ) O(m) O(m)，即主串的前 m m m 个字符正好等于模式串的 m m m 个字符。在最坏情况下的时间复杂度和平均时间复杂度均为 O ( n m ) O(nm) O(nm)。空间复杂度为 O ( 1 ) O(1) O(1)。

二、KMP算法

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

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

2.1 字符串基础

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

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

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

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

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

真前缀： 指除了 s s s 本身的 s 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 i,j i,j，但在BF算法的动画演示中，我们可以只考虑主串的指针 i i i，这是因为模式串每次都向右移动一位并与主串「网格对齐」，所以只需要比较 i i i 所指向的两个（对齐）网格中的元素，如下图所示：

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

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

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

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

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

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

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

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

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

模式串向右移动的距离 = j − j 的更新值 = j − n e x t [ j ] 模式串向右移动的距离=j-j\,的更新值=j-next[j] 模式串向右移动的距离=j−j的更新值=j−next[j]

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

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

读到这里，相信你已经发现， n e x t next next 数组只与模式串有关，且长度和模式串的长度相同。设模式串为 t t t， n e x t next 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公共真前后缀集合非空其他

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

2.3 KMP的实现

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

⚠️ 我们使用 nxt 代替 n e x t next next 防止不必要的冲突。

每次比较时，若 s [ i ] s[i] s[i] 与 t [ j ] t[j] t[j] 相等，则执行 i++, j++ 并继续比较；若不等，则执行 j = nxt[j] 以更新 j j j（相当于向右移动模式串）。一个特殊情况是，如果某一次比较出现了 s [ i ] s[i] s[i] 不等于 t [ 0 ] t[0] t[0]，即在模式串的第一个字符处失配，则 j j j 的更新值为 j = nxt[0] = -1，接下来应当执行 i++, j++，相当于让模式串右移一位并重新在模式串的第一个字符处进行比较。由此可见，定义 n e x t [ 0 ] = − 1 next[0]=-1 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数组的生成

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

因为 n e x t [ i ] = k next[i]=k next[i]=k，故 t [ 0.. k − 1 ] = t [ i − k . . i − 1 ] t[0..k-1]=t[i-k..i-1] t[0..k−1]=t[i−k..i−1]，下面分两种情况讨论：

情况一： t [ k ] = t [ i ] t[k]=t[i] t[k]=t[i]。此时有 t [ 0.. k ] = t [ i − k . . i ] t[0..k]=t[i-k..i] t[0..k]=t[i−k..i]，所以应有 n e x t [ i + 1 ] = k + 1 next[i+1]=k+1 next[i+1]=k+1。会不会还存在 t [ 0.. k + 1 ] = t [ i − k − 1.. i ] t[0..k+1]=t[i-k-1..i] t[0..k+1]=t[i−k−1..i] 这种情况使得 n e x t [ i + 1 ] = k + 2 next[i+1]=k+2 next[i+1]=k+2 呢？若存在，则可推得 t [ 0.. k ] = t [ i − k − 1.. i − 1 ] t[0..k]=t[i-k-1..i-1] t[0..k]=t[i−k−1..i−1]，这说明 n e x t [ i ] = k + 1 next[i]=k+1 next[i]=k+1，与 n e x t [ i ] = k next[i]=k next[i]=k 矛盾。情况二： t [ k ] ≠ t [ i ] t[k]\neq t[i] t[k]=t[i]。记 k 1 ≜ n e x t [ k ] k_1\triangleq next[k] k1≜next[k]，于是有 t [ 0.. k 1 − 1 ] = t [ k − k 1 . . k − 1 ] t[0..k_1-1]=t[k-k_1..k-1] t[0..k1−1]=t[k−k1..k−1]，又因 t [ 0.. k − 1 ] = t [ i − k . . i − 1 ] t[0..k-1]=t[i-k..i-1] t[0..k−1]=t[i−k..i−1]，故有 t [ 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[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[0..k1−1]=t[k−k1..k−1]=t[i−k..i−k+k1−1]=t[i−k1..i−1]，即 t [ 0.. k 1 − 1 ] = t [ i − k 1 . . i − 1 ] t[0..k_1-1]=t[i-k_1..i-1] t[0..k1−1]=t[i−k1..i−1]。若 t [ k 1 ] = t [ i ] t[k_1]=t[i] t[k1]=t[i]，则根据情况一， n e x t [ i + 1 ] = k 1 + 1 next[i+1]=k_1+1 next[i+1]=k1+1；若 t [ k 1 ] ≠ t [ i ] t[k_1]\neq t[i] t[k1]=t[i]，则记 k 2 ≜ n e x t [ k 1 ] k_2\triangleq next[k_1] k2≜next[k1]，重复执行情况二的操作。若在某一步发现 k n = − 1 k_n=-1 kn=−1，说明已经回退到了 t t t 的开头，此时应置 n e x t [ i + 1 ] = 0 next[i+1]=0 next[i+1]=0。

求解 n e x t next 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(m) O(m)，平均时间复杂度为 O ( n + m ) O(n+m) O(n+m)，最坏时间复杂度仍为 O ( n m ) O(nm) O(nm)。空间复杂度为 O ( m ) O(m) O(m)。

三、改进的KMP算法

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

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

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

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

3.1 nextval数组

上述问题可以通过改进 n e x t next next 数组得到解决，将 n e x t next next 数组改为 n e x t v a l nextval nextval 数组。与 n e x t [ 0 ] next[0] next[0] 一样，先置 n e x t v a l [ 0 ] = − 1 nextval[0]=-1 nextval[0]=−1。

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

已知 s [ i ] ≠ t [ j ] s[i] \neq t[j] s[i]=t[j]，接下来分两种情况讨论：

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

求解 n e x t v a l nextval 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 ) O(n+m) O(n+m)。

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

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

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

4.1 前缀函数

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

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

不难发现 π \pi π 数组与 n e x t next next 数组之间的关系如下：

π [ i ] = { n e x t [ i + 1 ] , 0 ≤ i ≤ m − 2 t 的最长公共真前后缀的长度 , i = m − 1 \pi[i]= \begin{cases} next[i+1],&0\leq i \leq m - 2 \\ t \,的最长公共真前后缀的长度,&i=m-1 \\ \end{cases} π[i]={next[i+1],t的最长公共真前后缀的长度,0≤i≤m−2i=m−1

根据 π \pi π 的定义，一定有 π [ 0 ] = n e x t [ 1 ] = 0 \pi[0]=next[1]=0 π[0]=next[1]=0，于是求解 π \pi π 数组只需要求解 π [ 1.. m − 1 ] \pi[1..m-1] π[1..m−1]。

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

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

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

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

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

π [ i ] ≤ m , i > m \pi[i]\leq m,\quad i>m π[i]≤m,i>m

当 π [ i ] = m \pi[i]=m π[i]=m 时，意味着 t t t 完整出现在该位置，并且右端点位于 i i i 处。 此时 t t t 在 s s s 中的起始下标为 i − ( m − 1 ) − ( m + 1 ) = i − 2 m i-(m-1)-(m+1)=i-2m i−(m−1)−(m+1)=i−2m。于是我们只需要遍历 π \pi π 数组即可求得 t t 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 π 数组的生成

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

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

已知 t [ 0.. k − 1 ] = t [ i − k . . i − 1 ] t[0..k-1]=t[i-k..i-1] t[0..k−1]=t[i−k..i−1]，如果此时有 t [ k ] = t [ i ] t[k]=t[i] t[k]=t[i]，那么可得 π [ i ] = k + 1 \pi[i]=k+1 π[i]=k+1。如果 t [ k ] ≠ t [ i ] t[k]\neq t[i] t[k]=t[i]，记 k 1 ≜ π [ k − 1 ] k_1\triangleq \pi[k-1] k1≜π[k−1]，于是有 t [ 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[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[0..k1−1]=t[k−k1..k−1]=t[i−k..i−k+k1−1]=t[i−k1..i−1]，即 t [ 0.. k 1 − 1 ] = t [ i − k 1 . . i − 1 ] t[0..k_1-1]=t[i-k_1..i-1] t[0..k1−1]=t[i−k1..i−1]，如果此时 t [ k 1 ] = t [ i ] t[k_1]=t[i] t[k1]=t[i]，那么 π [ i ] = k 1 + 1 \pi[i]=k_1+1 π[i]=k1+1，否则记 k 2 ≜ π [ k 1 − 1 ] k_2\triangleq \pi[k_1-1] k2≜π[k1−1]，重复执行上述操作。

若在某一步出现了 k n = 0 k_n=0 kn=0，说明已经回退到了 t t t 的开头，此时应置 π [ i ] = 0 \pi[i]=0 π[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 n n 的数量级为 1 0 6 10^6 106， m m m 的数量级为 1 0 5 10^5 105。

#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/