算法笔记 KMP

什么是KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt几乎同时发现的一种字符串匹配算法。他要解决的是如下问题：
（模式串的匹配问题）在某个字符串S中，求字符串T出现的位置。其中字符串S叫做主串，字符串T叫做模式串。若字符串T在字符串S中出现，那么返回它第一次出现的位置。若没有出现，则返回-1。

例如：
```
主串S: ABCABCAB
模式串T: ABC
```
则模式串T在S中出现了2次，第一次出现的位置是0，即主串S中第一个A的位置。
如何解决

1.暴力法

我们很容易能想到一种解决方法：令i， j是两个分别指向主串S和模式串T的指针（即数组下标）。

第一步：令i，j初始化为0，即分别指向主串S和模式串T的开头。

第二步：

1^°若S[i] == T[j]，则将i和j分别自增1，为下一次比较做准备。

2^°若S[i] != T[j]，那么匹配失败（称为失配），i指向一开始时i的下一位，j需要重置为0。

第三步：循环第二步，若j == T.length()，说明找到了这个字符串，匹配成功，否则若i == S.length()，则说明找到主串S中的最后都没能匹配成功，即T在S中没有出现，返回-1。

算法如图所示：

据此算法，我们可以得出如下代码：
```
#include<bits/stdc++.h>
using namespace std;
int main(void){
	string s, t;
	cin >> s >> t;
	int i = 0, j = 0;
	int len1 = s.length(), len2 = t.length();
	while(i < len1 && j < len2){
		if(s[i] == t[j]){
			i++, j++;
		}
		else{
			i = i - j + 1;//j是指向当前模式串失配位置的指针，也就是主串和模式串匹配字符的个数
			//所以i-j表示将i退回至起点，+1即将i指向一开始i的下一位
			j = 0;//重置j为0 
		}	
	}
	if(j == len2){
		cout << i - j + 1 << endl;//输出在主串中模式串第一次出现的位置，i-j的含义和上面相同 
		//这里我们将下标从1开始，所以+1 
	}
	//j没有到达模式串的最后，说明没有匹配成功 
	else{ 
		cout << -1 << endl;
	}
	return 0;
}
```
这个算法在最坏情况下，每次比较都是比到模式串的最后一个字符，发现不匹配。如：
```
主串：aaaaaaaaaaaaaaaaaaaaaaab
模式串：aaaaab
```
这时最坏情况下的时间复杂度是O(mn)（m表示主串的长度，n表示模式串的长度）。当在处理百万量级长度的字符串时，这显然不够好，所以我们对算法进行优化。KMP算法便应运而生。

2.KMP算法

在朴素的暴力法中，当字符串失配时，总是只将指针i自增1，其实这是对已有信息的极大浪费。

在字符串失配的时候，其实已经知道主串和模式串的前j个字符是匹配的。那么我们能不能用这一信息，移动指针j，而指针i可以保留在失配的位置，而不用回到上一次i的后一位？

还是回到刚才的字符串，

如果我们人脑操作，在失配的时候，因为前两个字符A，B是适配的，所以我们不可能再将i指向第二个B，将j归零。我们可以直接将j指向第一个A，而不动i。（如图）然后继续比较。

这个例子可能还不是很清楚，考虑如下例子：

算法笔记 KMP

观察②到③的过程，我们没有直接把j放到模式串的第0位，而是从第1位开始比较。因为在②失配的时候，我们已经知道②的前三个字符和处在i指针前面的三个字符是匹配的，而j指针前的字符串中，本身它的第一个字符和最后一个字符是相同的。那么我们可以得到：

因为，第②步中，j指针前的字符串是和主串i之前的相同长度的字符串匹配
又因为，j指针前的字符串的第一个字符和最后一个字符相同
所以，模式串S的第一个字符和主串指针i之前的最后一个字符相匹配。

这是KMP算法的关键。其中j指针前的字符串第一个字符和最后一个字符相同，可以扩展为j指针前的字符串的前n个字符（称为前缀）和后n个字符（称为后缀）相同，那么模式串S中j指针的前n个字符就和主串指针i前的n个字符相同。

表述起来可能有点令人费解，看图。
算法笔记 KMP

所以，我们只要知道指针j前的字符串最长的相同前缀后缀的长度。每次失配的时候，我们只需将j指针移到最长相同前缀后缀之后的位置继续比较，而i指针不动，这样能大大减少算法运行的时间。

同时，如果某次失配时，j指针已经指向了模式串的开头，那么这个时候j指针已经无法移动了（j指针前的字符串为空串，最长相同前缀后缀长度一定为0，j指针永远为0），这时我们就要将i指针向后移动一位。如图中④到⑤步。

我们将指针j前的字符串的最长相同前缀后缀长度记录在next[i]数组中。由此我们可以得出KMP算法的代码。

int kmp_search(string s, string p){
	int i = 0;
	int j = 0;
	int len1 = s.length(), len2 = p.length();
	while(i < len1 && j < len2){
		if(j == -1 || s[i] == p[j]){//为什么会判断j是否等于-1？之后会讲
			i++, j++;//如果匹配，指针自增1
		}
		else{
			j = next[j];//不匹配了，j指针指向next[j]
		}
	}
	if(j == len2){//模式串匹配完了，即在主串中找到了模式串
		return i-j;//i-j是模式串第一次出现的位置
	}
	else
		return -1;//没找到，返回-1
}

那么我们现在的问题就转化成了求next[]数组，即求指针j前的字符串的最长相同前缀后缀的长度。这也是KMP算法的核心部分，也是最难理解的部分。

求指针j前的字符串的最长相同前缀后缀的长度，相当于一个模式串的长度为j的前缀和另一个相同的模式串进行匹配的过程。其中长度为j的前缀比较充当的是后缀的作用（这里比较难理解）。因为后缀一定是连续的，所以当该前缀的长度变大后，如果最后一个字符是匹配的，那么加上前面的匹配串的长度，就是对应长度为j的前缀的的最长相同前缀后缀的长度。（由已知状态推出未知状态，有点像动态规划）

我们用一个i（这里为了方便，j和i互换了）指针指向该前缀，那么i指针前的字符串和另一个与模式串相同的串的最大匹配的串长，就是next[i]的长度。注意，这里next[i]数组的下标i表示长度为i的前缀的最长相同前缀后缀的长度，即在这里，字符串第一个数字的i是1，而不是0。而匹配的模式串，下表从0开始。

和之前一样，文字叙述比较难理解，看图。（红字部分表示现在的模式串的长度为i的前缀，阴影部分表示匹配的部分）

首先我们将next[0]设为-1。-1是一个特征值，表示现在j指针已经指向了模式串的开头，此时要将i指针向后移动一位，这就是上面kmp_search()函数第5行判断j是否等于-1的原因。

由于单个字符的前缀是空串，所以next[1] = 0，我们从i=2开始处理
算法笔记 KMP

算法笔记 KMP

注意失配的时候，情况和匹配主串和模式串的方法相同。若配对成功，则i，j指针均自增1。若出现了失配，那么i指针不变，将j指针变为next[j]的数值，因为i从2开始，而j从1开始，并且i是单调增加的，且j增加的时候，i必定增加，所以必有j < i，即当失配时，所需求得得next[j]一定已经算好了（有点类似动态规划的思想）。这时我们将j置为next[j]。和主串和模式串匹配相同地，若j在模式串的开头，并且此时失配了，可以得到此时的j = -1，说明要将i自增1。

由此我们可以得到代码：

const int N = 1e6+7;
int next[N];
void getNext(string p){
	next[0] = -1;
	int i = 0, j = -1;
	int len = p.length();
	while(i < len){
		if(j == -1 || p[i] == p[j]){
			++i, ++j;
			next[i] = j;
		}
		else j = next[j];
	}
}

将getNext()函数和kmp_search()函数结合起来，就可以得到KMP的完整算法。

例题

洛谷P3375 【模板】KMP字符串匹配

题目描述

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。
输入输出格式
- 输入格式
第一行为一个字符串，即为s1

第二行为一个字符串，即为s2
- 输出格式
若干行，每行包含一个整数，表示s2在s1中出现的位置

接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
输入输出样例
- 输入样例#1：
```
ABABABC
ABA
```
- 输出样例#1：
```
1
3
0 0 1 
```
说明

时空限制：1000ms,128M

数据规模：

设s1长度为N，s2长度为M

对于30%的数据：N<=15，M<=5

对于70%的数据：N<=10000，M<=100

对于100%的数据：N<=1000000，M<=1000000
Tips:

这题和标准KMP的不同之处在于要输出所有的匹配，而不是第一个匹配的位置，多用几次KMP循环即可。

Answer:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int next[N];
void getNext(string p){
	next[0] = -1;
	int i = 0, j = -1;
	int len = p.length();
	while(i < len){
		if(j == -1 || p[i] == p[j]){
			++i, ++j;
			next[i] = j;
		}
		else j = next[j];
	}
}
int kmp_search(string s, string p, int i){
	int j = 0;
	int len1 = s.length(), len2 = p.length();
	while(i < len1 && j < len2){
		if(j == -1 || s[i] == p[j]){
			i++, j++;
		}
		else{
			j = next[j];
		}
	}
	if(j == len2){
		return i-j;
	}
	else
		return -1;
}
int main(void){

	string s, p;
	cin >> s >> p;
	getNext(p);
	int i = 0;
	while(true){
		i = kmp_search(s, p, i);
		if(i == -1){
			break;
		}
		else{
			cout << i + 1 << endl;
			i++;
		}
	}
	for(unsigned int k = 1; k <= p.length(); k++){
		cout << next[k] << ' ';
	}
	cout << endl;
	return 0;
}

算法笔记 KMP

算法笔记 KMP

洛谷P3375 【模板】KMP字符串匹配

相关推荐