• 本文为博主原创，未经许可不得转载

概述

　　KMP算法由Knuth、Morris、Pratt三人提出，为了解决字符串匹配问题，但是对于初学者难以理解，我也是先后学了多次才理解

　　KMP要解决的问题是：给定两个字符串$A$和$B$，长度分别为$n$和$m$，判断$B$是否在$A$中出现过

　　常规的方法是遍历A中的每一个位置进行匹配，时间复杂度$O(n^2)$

　　这样的方法效率很低，我们要想办法降低它的时间复杂度，这就是KMP算法诞生的意义

算法原理

从朴素算法说起

　　朴素做法是遍历A中的每一个位置进行匹配，时间复杂度$O(n^2)$

　　考虑这样做为什么效率低下，时间究竟浪费在了什么地方？

　　事实上，朴素算法中失配时的选择是B串后移一位，重新匹配，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高

　　那么我们考虑是否可以通过记录已经通过匹配获得到的信息，使得失配时从B串后移k位，然后继续开始匹配，而不是B串仅仅后移一位

　　这就是优化算法的突破口

字符串的boder

　　通过上面的分析，我们知道可以在失配时将B串后移一位，然后重新开始匹配

　　设已经匹配的部分为S，失配后B串移动k为后，和A串匹配的部分为F

　　接下来，我们分析F需要满足什么样的条件，请看下图

　　不难发现，F既是S的前缀又是S的后缀

　　我们把既是前缀又是后缀的子串称作字符串的boder

　　也就是说，我们可以预处理出B串的每个前缀的最长boder，然后和A串匹配，如果失配就将B串前移，令B串在当前失配位置的最长boder和A串匹配，然后继续匹配

　　代码也很容易实现：

1
2
3
4
5

for(int i=1,j=0;i<=n;++i){
	while(a[i]!=b[j+1]&&j)  j=pre[j];//如果失配，返回boder处
	if(a[i]==b[j+1])  ++j;//如果匹配上了，指针右移
	if(j==m)  ans=1;
}

预处理boder

　　现在的问题就是给定一个串，我们如何预处理出该串的最长boder

　　实际上求最长boder的过程是一个字符串自我匹配的过程

　　假设我们现在已经求得pre[1]~pre[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求pre[i+1]

　　如果A[i+1]==A[next[i]+1]，那么显然pre[i+1]=pre[i]+1

　　如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。

　　代码实现和上面的代码神似

1
2
3
4

for(int i=2,j=0;i<=m;++i){
	while(b[j+1]!=b[i]&&j)  j=pre[j];
	if(b[j+1]==b[i])  ++j;  pre[i]=j;
}

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN (int)1e5+10
using namespace std;
int n,m,ans,pre[MAXN];
char a[MAXN],b[MAXN];
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%s%s",a+1,b+1);  n=strlen(a+1); m=strlen(b+1); 
	for(int i=2,j=0;i<=m;++i){
		while(b[j+1]!=b[i]&&j)  j=pre[j];
		if(b[j+1]==b[i])  ++j;  pre[i]=j;
	}
	for(int i=1,j=0;i<=n;++i){
		while(a[i]!=b[j+1]&&j)  j=pre[j];//如果失配，返回boder处
		if(a[i]==b[j+1])  ++j;//如果匹配上了，指针右移
		if(j==m)  ans=1;
	}
	printf("%d\n",ans);
	return 0;
}

时间复杂度分析

　　kmp的时间复杂度是线性的，但是从代码中很难看出，为此我们来分析一下kmp的时间复杂度

　　首先枚举匹配位置是线性的，唯一不确定的因素就是$j$指针的回溯

　　注意到$pre[j]<j$，所以每次回溯，$j$指针至少减去$1$，而每次匹配$j$指针只增加$1$，并且保证$j$非负，所以$j$减少的次数不会超过增加的次数

　　而$j$增加的次数最多是$m$，也就是说$j$回溯的次数必定小于$m$，所以回溯的复杂度是$O(m)$的

　　所以kmp的时间复杂度是$O(n+m)$，这也就是该问题的时间复杂度的下线

kmp自动机

　　当我们求出pre数组后，将pre[i]向i连边，整张图构成了一颗有n+1个节点的树。

　　其中，０号点为根，从根到ｉ路径上的点都是A[1~i]的boder，于是在统计与boder相关的问题时就可以沿着这棵树进行贡献转移

　　上述结构成为kmp自动机，这个自动机可识别所有的boder

参考文献

• 《浅谈字符串匹配的几种方法》——王鉴浩的15年集训队论文
• 《KMP算法详解》——yutianzuijin 传送门
• 《KMP算法详解》——Matrix67 传送门
• 《kmp算法总结》——ddyyxx 传送门