kmp
注:本篇文章只记录我理解的过程、需要注意的小细节,不涉及具体讲解,一些具体的原理、推导步骤可参考文末我列出的文章和视频
说到字符串匹配,以前的我,对时间、空间复杂度没有什么概念,估计写出来的代码长这样
BF(brute-force)
int BF(string s, string p) {
int len1 = s.length();
int len2 = p.length();
int i = 0; j = 0;
while (i < len1 && j < len2) {
if (s[i] == p[j]) {
i++, j++;
// 匹配成功就指针都后移
} else {
i = i - j + 1;
j = 0;
}
}
if (j == len2)
return 1;
else
return -1;
}
查阅资料后发现,这¥%&#时间复杂度还挺高,假设文本串长m,模式串长n,时间复杂度是O(m*n)
,如果m和n都很大的话,效率会低到无法想象
kmp
这时候,引入一个新算法,kmp,反正就是三个大佬的名字首字母拼在一起
要理解kmp,首先要理解kmp中的next数组,next数组,说人话,就类似一个索引。kmp的本质就是利用模式串的最长公共前后缀来缩短查找时间
如果字符失配,模式串向后移动j-next[j]
位,这样说还不是很好理解,看一个例子
a | b | c | d | a | b | a | b | c | d | a | b | c | d | a | b | d | e |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | a | b | d |
这里在第七位失配,在d前面,有最长公共前后缀"ab",长度为2,按照刚才说的,模式串向后移动j-next[j]
位,即6-next[6]
,其中next[6] = 2
,变成如下
a | b | c | d | a | b | a | b | c | d | a | b | c | d | a | b | d | e |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | a | b | d |
c失配,c前无最长公共前后缀,向后移动2-next[2]
,也就是2位
a | b | c | d | a | b | a | b | c | d | a | b | c | d | a | b | d | e |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | a | b | d |
在d处又失配,再次移动6-next[6]
也就是4位
a | b | c | d | a | b | a | b | c | d | a | b | c | d | a | b | d | e |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | a | b | d |
匹配成功ヾ(≧▽≦*)o
以上就是kmp算法的基本实现流程
next
next数组的二三事
next数组的实质是:在当前字符前,最长公共前后缀的字符数
先拿出一个模式串:abcabzan
对于next,有些版本默认第0位是-1,有的是0,这里默认第0位是-1.
- 对于第一位是a,前面没有字符,赋值-1
- 第二位b前面只有一个字符,没有相同子串,赋值0
- 第三位前面两个字符没有同,赋值0
- 第四位前面也无,同上
- 第五位前面有相同前后缀元素,即a,赋值1
- 第六位前面,继续找,发现有更长的前后缀公共元素,是ab,两个字符,赋值2
- 第七位无,第八位前有一个a,赋值1,后面无公共元素
- 一般来说不用管最后一位是否和前面的字符能匹配上,next的目的是判断当前字符前面是否有相同的子串
最后把next数组的值罗列一下
-1 0 0 0 1 2 0 1
然后就得到了next数组
next数组代码实现
void makeNext(string p, int next[]) {
int j = 0, k = -1;
int len = p.length();
next[0] = -1;
while (j < len - 1) {
if (k == -1 || p[j] == p[k]) {
// 这里判断是否从首位开始匹配,或者模式串前后是否匹配成功
j++, k++;
next[j] = k;
// 匹配成功就把当前匹配的字符数赋给当前next[j]
// 即模式串第j位前有k个最长前后缀公共元素
} else {
k = next[k];
// 把当前next[k]赋给k,也就相当于整个模式串向后移动next[k]位
}
}
}
next数组的优化
a | b | a | c | a | b | a | b | c |
---|---|---|---|---|---|---|---|---|
a | b | a | b |
对于模式串"abab"
,它的next数组为-1 0 0 1
当c与b失配时,模式串向后移动3-next[3] = 2
,变成如下
a | b | a | c | a | b | a | b | c |
---|---|---|---|---|---|---|---|---|
a | b | a | b |
看到上面这里,原来p[j]
和s[j]
失配,右移之后,变成s[j]
和p[next[j]]
(即前后缀相同字符)匹配,然后呢,又失配了,虽然说在这组字符串里最后都能匹配成功,但是移动后,按照道理,失配位前面的字符在移动之后都能匹配成功,如果一直出现这样的情况的话,那么匹配的效率就会下降。
那么怎么修改?答案是,不能容许p[j]=p[next[j]]
。如果出现刚才叙述的情况,则需递归,令next[j] = next[next[j]]
那么这个递归又是怎么个回事呢?(看了好久才懂)
随便举一个字符串ababc
下标从0开始,到c这个位置,也就是第4位,下标为1的字符b和下标为3的字符b是等价的,在递归之后,next数组更新,可避免出现刚才那样的bug,后移之后在前面的子串部分失配(按照道理,公共前后缀部分是不会失配的)
void makeNext(string p, int next[]) {
int len = p.length();
int k = -1, j = 0;
next[0] = -1;
while (j < len - 1) {
if (k == -1 || p[j] == p[k]) {
j++, k++;
if (p[j] != p[k])
next[j] = k;
// 如果匹配失败就把匹配数赋给next[j]
else
next[j] = next[k];
// 不能出现p[j] = p[next[j]]的情况,需要继续递归
} else {
k = next[k];
// 把k复位(分匹配是否成功两种情况)
}
}
}
优化过后的数组
a | b | a | b |
---|---|---|---|
-1 | 0 | -1 | 0 |
单单只看优化过后的代码,感觉还是有点恍惚,还是要结合kmp的主干部分来看
kmp
int kmp(string s, string p) {
int len1 = s.length();
int len2 = p.length();
int i = 0, j = 0;
int *next = new int[len2];
makeNext(p, next);
while (i < len1 && j < len2) {
// j为-1 or 匹配成功才指针后移
if(j == -1 || s[i] == p[j])
i++, j++;
// 匹配就指针后移
else
j = next[j];
// 不匹配就根据之前求出的next来决定模式串从哪开始匹配
}
if (j == len2)
return 1;
else
return 0;
}
优化过后继续结合刚才优化前出现bug的那个数组
优化后next:-1 0 -1 0
a | b | a | c | a | b | a | b | c |
---|---|---|---|---|---|---|---|---|
a | b | a | b | |||||
-1 | 0 | -1 | 0 |
第四位失配,后移3-next[3]
,递归后next[3] = 0
,后移了3位
a | b | a | c | a | b | a | b | c |
---|---|---|---|---|---|---|---|---|
a | b | a | b | |||||
-1 | 0 | -1 | 0 |
c和a失配,再后移
a | b | a | c | a | b | a | b | c |
---|---|---|---|---|---|---|---|---|
a | b | a | b | |||||
-1 | 0 | -1 | 0 |
匹配成功
完整代码
#include <bits/stdc++.h>
using namespace std;
void makeNext(string p, int next[]);
int kmp(string s, string p);
void makeNext(string p, int next[]) {
int len = p.length();
int j = 0, k = -1;
next[0] = -1;
while (j < len - 1) {
if (k == -1 || p[j] == p[k]) {
j++, k++;
if (p[j] != p[k])
next[j] = next[k];
else
k = next[j];
}
}
}
int kmp(string s, string p) {
int len1 = s.length();
int len2 = p.length();
int i = 0, j = 0;
int *next = new int[len2];
makeNext(p, next);
while (i < len1 && j < len2) {
if (j == -1 || s[i] == p[j])
i++, j++;
else
j = next[j];
}
if (j == len2)
return 1;
else
return 0;
}
int main() {
string s, p;
cin >> s >> p;
if (kmp(s, p) == 1)
cout << "found the key string\n";
else
cout << "not found the key string\n";
}