ACM算法基础-kmp算法详解

kmp算法详解

问题背景：kmp算法最直接的引用就是模式串和文本串的匹配，我们假设直接用暴力的方法进行匹配的话，方法很简单，就是两个指针，$i$指针最初指向文本串的起始位置，$j$指针最初指向模式串的起始位置，然后从文本串的起始位置开始每一位与模式串的每一位进行匹配，如果每一位都是相同的话，那么就继续匹配下一位，当我们只要匹配到有一位是不相等的时候，我们就将文本串的起始位置变成$i+1$，然后继续从模式串的起始位置开始匹配，假设模式串和文本串的长度分别是$n$和$m$，时间复杂度是$O(nm)$​,暴力确实太可怕了。

我们先来看看暴力解法（请耐心看完，对后面理解kmp算法很有帮助）

#include<iostream>
#include<string>
using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s, p;
	cin >> s >> p;//分别读入模式串和匹配串
	int ls = s.size(), lp = p.size();
	bool flag = false;//假设刚开始的时候匹配不成功
	for (int i = 0, j = 0; i < ls; i++) {
		while (s[i + j] == p[j]&& j < lp) j++;//模式串和匹配串的每一位相同我们就一直往后面匹配，但是我们匹配到匹配串的最后一位是要退出
		if (j == lp) {
			flag = true;
			cout << "匹配成功" << endl;
			break;
		}
		if (s[i + j] != p[j]) {//如果匹配到模式串和匹配串的某一位不相同，则从模式串的下一位开始匹配，匹配串从初始位置开始
			j = 0;
		}
	}
	if (!flag)
		cout << "匹配不成功" << endl;
	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

基本概念

在学习kmp算法之前，我们首先要明确字符串中的一些基本概念，下面详细讲述一下这些概念。

1：前缀和后缀

首先明确前缀和后缀是不包括$字符串本身$的；(假设字符串的长度是$n$，下标从1开始，$q[1,i]$代表字符串的下标从1-$i$)

前缀 $q[1,i]$​ $i<n$​​;

后缀 $h[j,n]$ $j>1$;

2：$next[]$​​​数组

$next[i]$​代表的含义是下标从1到$i$​的字符串中前缀和后缀相等的最大长度

假如$next[i]=j$，则$p[1,j]=p[i-j+1,i]$​

kmp算法的具体实现

其实kmp算法和暴力算法之间优化就是当模式串和文本串不能匹配的时候，暴力算法只能将文本串往后面移动一位，模式串从起始位置重新开始匹配。但是kmp算法能够使$j$指针移动到它该到的位置，下面结合图来讲解；

我们读入字符串的时候都是从下标1开始读入的，所以我们的$j$不能移动到0，这个一定要注意。

当我们匹配到绿线的时候，我们文本串和模式串是完全匹配的，但是$s[i]!=p[j+1]$​，所以接下来我们就要考虑将$j$​指针移动到那个位置保证模式串的$[1,j]$​和文本串的$[i-j,i-1]$​是完全匹配的，我们只需要将$j$​移动到$ne[j]$​的位置即可，($ne[j]$表示的是紫色的那一段，含义就是1-j中前缀和后缀相等的最大长度)然后继续将$s[i]$与$p[j+1]$​​进行匹配，如果还是不能匹配的话，我们就重复上面的操作就行。

通过kmp算法，我们的是将复杂度降到了$O(n+m)$

举例

next[]数组的求解

$next[]$数组只涉及到模式串，其实求解的方法和匹配过程是一样的，唯一的不同就是它的求解是模式串和模式串自己进行匹配，每一次需要将$next[i]$​保存下来，然后为了后面匹配的时候可以直接取出来用。
求解的时候从下标2开始，因为$next[1]$=0，我们不需要求解$next[1]$了。

具体代码

#include<iostream>
using namespace std;

const int N = 10010, M = 1000010;
char p[N], s[M];
int ne[N];

int main() {
	cin >> p + 1 >> s + 1;//从下标1开始读入模式串和文本串
	int lp = strlen(p + 1), ls = strlen(s + 1);

	//求解next数组
	for (int i = 2, j = 0; i <= lp; i++) {//i可以从2开始，因为ne[1]=0;
		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 <= ls; i++) {
		while (j && s[i] != p[j + 1])j = ne[j];
		if (s[i] == p[j + 1])j++;
		if (j == lp) {
			//题目的具体实现

			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

最后感谢大家的点赞收藏和关注。