【字符串】总结KMP算法

buildtime:2019年7月15日

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

先放两篇比较好的资料:

从头到尾彻底理解KMP（2014年8月22日版）

[KMP算法]NEXT数列手算演示

KMP的算法流程：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

  • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
  • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。

计算NEXT数组流程：

将前缀后缀相同数组去掉最后一个值，在前面加上-1即可（某些版本还有总体+1）

代码：

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
#include<bits/stdc++.h>
using namespace std;
const int N=1000024;
string a,b;
int next[N],n,k;
inline void Getnext()//针对子串 
{ 
	int i=0,j=-1;
	next[0]=-1;
	while(i<b.length())//从头到尾 
	  if(j==-1 || b[i]==b[j])//匹配成功，继续下一个字符 
	      next[++i]=++j;
	  else j=next[j];//不成功，回调再匹配
}
inline void KMP()
{
	int i=0,j=0;
	while(i<a.length())
	{
		if(j==-1 || a[i]==b[j])//j==-1（开头跳位）或a[i]==b[j]匹配成功，令i++，j++，继续匹配下一个字符 
			i++,j++;
		else j=next[j];//不成功，进行合理移动，再来一遍 
		if(j==b.length())//末尾成功，整串成功，输出结果并移动再继续 
		{
			j=next[j];
			cout<<i-b.length()+1<<endl;//母串位置-子串长度+1 
		}
	}
}
int main()
{
	cin>>a>>b;
	Getnext();
	KMP();
	for(int i=1;i<=b.length();++i) 
        printf("%d ",next[i]);//输出next数组（实际上不同版本有不同），此处真正使用的部分是 0~lenb-1 
    return 0;
}