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";
}