数据结构：KMP(考研 + 竞赛)
1.KMP
KMP，一个让无数考研科班学子闻风丧胆的匹配算法，但也正应和了高中老班经常说的那样，很难的东西，考察起来会很简单，KMP在408中只考察过两次，且考察方式十分的简单，本文分为两个方面，第一大模块介绍考研中需要掌握的KMP，学有余力的同学可以看一下第二部分，KMP的代码实现，本文会对KMP的描述十分的详细 (因为博主怕以后忘记，咳咳咳，还得靠这篇复习)
2.考研KMP
考研中对KMP的考察为：会简单模拟KMP过程，并且可求出KMP的next数组即可
2.1.什么是KMP
KMP是对朴素版字符串匹配算法的优化，我们这里还是举栗子说明：
下面小故事的场景为一个班级中有一位老师(晶姐)，两个学生：聪明的博主以及枭哥
晶姐今天丢给博主和枭哥两个人一个问题：
“这儿有两个字符串，字符串P是ababa，字符串Q是aba，现在你们两个给我找出来P中所有出现Q的位置，并且告诉我怎么找出来的”，说罢，便走到一旁开始喝茶。
听完这个问题，枭哥立刻站起来，说：“老师，我有一个笨办法”
好家伙，这可把博主吓了一跳：这人脑子啥时候这么好了 (不是
枭哥可不管博主心里怎么想，继续说到："设两个字符串的起点分别为i和j，然后依次对比，如果P[i] == Q[j]的话，就继续往后匹配，执行i ++， j ++，否则的话，让i移动到i最开始位置的后一个位置(即i最开始 = 1，比如发生不匹配的时候i = 3，那么让i = 2)，然后让j的值重新指回1"
晶姐点了点头 “不错，这个是个方法，直接暴力的去做就可以，假设P的长度为n，Q的长度为m，那么，时间复杂度为：O(nm)，辰chen，你有什么想法么？”
果然，还是得看聪明的我 (逃
“枭哥的办法太笨了”，博主悠悠站起身 “接下来请欣赏我的表演”
“枭哥这个办法时间复杂度太高，为什么高呢？因为对于每次发生不匹配的情况的时候，i都需要回溯，我们如果可以设计出这么一个东西，可以不让i发生回溯，即我们的i值只能一直变大直到遍历完整个P串，那么我们的算法显然是要变快了不少”
晶姐继续问道：“那应该怎么处理才能让i不发生回溯呢？”
“啊这，这就不知道了”，博主说到
那你装 ** 呢！？”，枭哥吼道
“咳咳”
“好啦好啦，都安静，辰chen的思维还是很不错的，这个思维就叫做KMP算法，即不让i发生回溯，i是始终往后走的，KMP的时间复杂度为O(n + m)，下面就让老师给大家讲解KMP算法中，辰chen不会处理的地方究竟是什么”
2.2.next数组
首先声明一点：本文中所有的字符串(数组)，下标均为从1开始，并非从0开始，这一点需要 注意再注意
KMP算法的核心就是next数组，介绍next数组之前，引入几个概念：子串，前缀，后缀
子串：串中任意多个 连续 的字符组成的子序列称为该串的子串
前缀：除了最后一个字符，字符串所有的头部子串
后缀：除了第一个字符，字符串所有的尾部子串
只有Q(短串)才有next数组，因为我们要求KMP算法中，长串的i不发生回溯，下面介绍next数组：
数组的定义：next[j]表示的为串的[1 ~ j - 1]中前后缀相等的最大长度 + 1，特别的，我们规定next[1] = 0
桥都嘛得！！！，看不懂上面说的么得关系，下面举栗子就懂了：
比如我们的Q串为：abaabc
next[1] = 0（特殊规定）
next[2]：按照上述定义为串的[1 ~ 1]中的前后缀相等的最大长度 + 1，显然，按照前后缀的定义，[1 ~ 1]的前后缀都为空，故前后缀相等的最大长度为0，即next[2] = 1
next[3]：串[1 ~ 2]为ab，前缀为a，后缀为b，显然a != b，故next[3] = 1
next[4]：串[1 ~ 3]为aba，前缀有三个：ab，a，空；后缀有三个ba，a，空，显然ab != ba，但是有a == a，即前后缀相等的最大长度为1，故next[4] = 2
next[5]：串[1 ~ 4]为abaa，前缀分别为：aba，ab，a，空；后缀分别为：baa，aa，a，空；显然，前后缀相等的最大长度还是1，故next[5] = 2
next[6]：串[1 ~ 5]为abaab，前缀分别为：abaa，aba，ab，a，空；后缀分别为：baab，aab，ab，b，空；显然有前缀ab和后缀ab是相等的，故前后缀相等的最大长度为2，即next[6] = 3
这就是我们预处理的next数组，按照上述栗子模拟后，大家应该懂得next数组应该如何去求了，next[1] = 0为特殊规定，其余的next[i] = 串的[1 ~ j - 1]中前后缀相等的最大长度 + 1，对于考研而言，能够自己手动去模拟next数组如何去求已经足够了，下面给出两个例题，读者可以自己动手求一下next数组，按照答案进行对比：
1.串aaab的next数组值
2.串ababaaababaa的next数组值
答案：
1.0123
2.011234223456
大家还可以发现一个有趣的规律：next[2] 恒等于 1
这里再强调一个点，有的书是规定next[1] = -1，那么我们只需要让next数组中所有的值都减去1即可
2.3.手动模拟KMP
知道如何求出next数组之后，对于考研，我们还需要知道如何模拟KMP的过程，我们还是举栗子去说明：
P：abaacabacabaabc
Q：abaabc
刚才我们已经求得了Q的next数组，接下来，我们开始比较，令i = 1(指向P的第一个位置)，j = 1(指向Q的第一个位置)，只要相等，就让i ++, j ++;，否则，我们让i不变，j = next[j]，可能大家看到这里很懵，不知道为什么要让j = next[j]，我们动手模拟一下就会知道了：
观察P和Q，那么当i == 5, j == 5的时候发生不匹配，我们要求i不变，让j = next[j]，即j退回到j = 2，这时候对P的第5个位置和Q的第2个位置继续进行比较即可，为什么呢？因为当我们的next指的为前后缀相等的最大长度 + 1，当我们的第j个位置发生不匹配，证明前[1 ~ j - 1]都是匹配的
如图所示，我们只需要让c和b比较即可，相当于当我们发生不匹配的时候，我们去看当前Q的前缀，找到前后缀相等最大的值然后比较后一位，比如上述图片中，前缀为abaa，前后缀想等的最大值为1，那么我们从1 + 1的位置进行比较即可
继续比较会发现，我们的j最终变成了0，那么这个时候，就证明包涵i这个位置的所有子串都不能和Q相匹配，故让i ++, j ++;
读者可以自己下去模拟后续的匹配过程，一定要自己手动模拟才可以理解KMP的奥义！
3.深入理解KMP
3.1.KMP模板
关于KMP，听了王道的课，听了AcWing的课，感觉起来还是王道的课要更容易理解一些，这里给出王道的KMP模板和AcWing的KMP模板，读者可以自行比较考虑，王道的模板为C语言，AcWing为C++，关于模板：直接背即可
3.1.1.王道模板
void get_next (String T, int next[]){
int i = 1, j = 0;
next[1] = 0;
while (i < T.length){
if (j == 0 || T.cj[i] == T.ch[j]){
++ i; ++ j;
next[i] = j;
}
else
j = next[j];
}
}
int Index_KMP (String S, String T, int next[]){ //S为长串，T为短串
int i = 1, j = 1;
while (i <= S.length && j <= T.length){
if (j == 0 || S.ch[i] == T.ch[j]){
++ i; ++ j;
}
else
j = next[j];
}
if (j > T.length)
return i - T.length;
else
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
3.1.2.AcWing模板
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
3.2.KMP优化：nextval
这里还是再举一个栗子说明：
比如模式串Qaaab和主串Paaabaaaaab进行匹配，我们可以求得next为：01234，
进行匹配的过程中，当i = 4, j = 4的时候发生失配，如果我们还是利用next数组让j发生回溯的话，我们还需要进行P4和Q3，P4和Q2，P4和Q1这三次比较，但是，事实上，因为Q1 = Q2 = Q3 = Q4的原因，当我们发生P4 ！= Q4的时候，完全没必要再把Q1，Q2，Q3和P4进行比较，拿同样相同的字符进行比较是毫无意义的，故我们处理nextval数组：特别的，对于j = 1，我们令nextval[1] = 0;我们如果发现Q[next[j]] == Q[j]，我们就让nextval[j] = nextval[next[j]];，否则nextval[j] = next[j]，故上述例子中，我们的nextval数组为：00004
3.2.1.模板1
void get_nextval(String T, int nextval){
nextval[1] = 0;
for (int j = 2; j <= T.length; j ++ )
{
if (T.ch[next[j]] == T.ch[j])
nextval[j] = nextval[next[j]];
else nextval[j] = next[j];
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
3.2.2.模板2
void get_nextval(String T, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0;
while (i < T.length){
if (j == 0 || T.ch[i] == T.ch[j]){
++ i; ++ j;
if (T.ch[i] != T.ch[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else
j = nextval[j];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
3.3.题目
注：C++的头文件下有next函数，为了避免重名问题，next在代码中写成ne，nextval在代码中写成neval
本题链接：AcWing 831. KMP字符串
本博客提供本题截图：
3.3.1.debug版
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N = 100010, M = 1000010;
int ne[N];
int neval[N];
char p[N], s[M];
int res;
int main()
{
int l1, l2;
cin >> l1 >> p + 1 >> l2 >> s + 1;
//求ne数组
int i = 1, j = 0;
ne[1] = 0;
while (i <= l1)
{
if (j == 0 || p[i] == p[j])
{
++ i; ++ j;
ne[i] = j;
}
else j = ne[j];
}
//求neval数组
/*
i = 1, j = 0;
neval[1] = 0;
while(i <= l1)
{
if (j == 0 || p[i] == p[j])
{
++ i; ++ j;
if (p[i] != p[j]) neval[i] = j;
else neval[i] = neval[j];
}
else j = neval[j];
}
*/
neval[1] = 0;
for (int j = 2; j <= l1 + 1; j ++ )
{
if (p[ne[j]] == p[j])
neval[j] = neval[ne[j]];
else neval[j] = ne[j];
}
//kmp算法
i = 1, j = 1;
while (i <= l2)
{
if (j == 0 || s[i] == p[j])
{
++ i;
++ j;
}
else j = neval[j];
//printf("i = %d, j = %d\n", i, j);
if (j > l1)
{
//printf("%d ", i);
//printf("%d,此时的i是：%d，此时的j是：%d\n", i - l1 - 1, i, j);
//res ++;
j = neval[j];
printf("%d ", i - l1 - 1);
//printf("ne[j] = %d , j = %d\n", ne[j], j);
}
//printf("%d\n", j);
}
//printf("%d", ne[4]);
//for (int i = 1; i <= 5; i ++ ) printf("%d ", ne[i]);
//for (int i = 1; i <= 3; i ++ ) printf("%c ", p[i]);
//printf("%d", res);
//for (int i = 1; i <= 6; i ++ ) printf("%d ", neval[i]);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
3.3.2.AcWing模板版
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int main()
{
int n, m;
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[j + 1] != p[i]) j = ne[j];
if (p[j + 1] == p[i]) j ++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && p[j + 1] != s[i]) j = ne[j];
if (p[j + 1] == s[i]) j ++;
if (j == n)
{
cout << i - n << ' ';
j = ne[j];
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
3.3.3.王道版next
王道版的next数组需要多处理一位，否则不对，比如对于aba，我们按上述定义只需要求三位next，本题需要求四位，即我们需要求出aba的前后缀相等的最大长度 + 1，只需要略微改变while，for循环条件即可
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N = 100010, M = 1000010;
int ne[N];
int neval[N];
char p[N], s[M];
int main()
{
int l1, l2;
cin >> l1 >> p + 1 >> l2 >> s + 1;
//求ne数组
int i = 1, j = 0;
ne[1] = 0;
while (i <= l1)
{
if (j == 0 || p[i] == p[j])
{
++ i; ++ j;
ne[i] = j;
}
else j = ne[j];
}
//kmp算法
i = 1, j = 1;
while (i <= l2)
{
if (j == 0 || s[i] == p[j])
{
++ i;
++ j;
}
else j = ne[j];
if (j > l1)
{
j = ne[j];
printf("%d ", i - l1 - 1);
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
3.3.4.王道版nextval
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N = 100010, M = 1000010;
int ne[N];
int neval[N];
char p[N], s[M];
int main()
{
int l1, l2;
cin >> l1 >> p + 1 >> l2 >> s + 1;
//求ne数组
int i = 1, j = 0;
ne[1] = 0;
while (i <= l1)
{
if (j == 0 || p[i] == p[j])
{
++ i; ++ j;
ne[i] = j;
}
else j = ne[j];
}
//求neval数组
neval[1] = 0;
for (int j = 2; j <= l1 + 1; j ++ )
{
if (p[ne[j]] == p[j])
neval[j] = neval[ne[j]];
else neval[j] = ne[j];
}
//kmp算法
i = 1, j = 1;
while (i <= l2)
{
if (j == 0 || s[i] == p[j])
{
++ i;
++ j;
}
else j = neval[j];
if (j > l1)
{
j = neval[j];
printf("%d ", i - l1 - 1);
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。
原文链接：chen-ac.blog.csdn.net/article/details/121435176
- 点赞
- 收藏
- 关注作者
评论（0）