🧑💻 文章作者:Iareges
🔗 博客主页:/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] /yyzsir/article/details/89462339
[2] 数据结构教程(Python语言描述)
[3] https://oi-/string/basic/
[4] /video/BV1AY4y157yL
[5] https://oi-/string/kmp/