字符串匹配算法之kmp

缘起

大家都使用过word吧? 如果要在整篇文档中搜索一个单词，比如就叫”word”,你会怎么搜索呢? 肯定是匹配咯~ 怎么匹配呢? 一种朴（bao）素（li）的算法就是指针指向整篇文档的第一个字符，然后和”word”进行匹配，至多最坏需要匹配4次，所以如果文档的字符个数是N，而搜索的单词的字符数是M的话，暴力算法（下简称BF算法，brute force）的复杂度将是O(NM)。 N,M比较小还好，如果一旦比较大的话，则这是程序不能忍受的. 其实你仔细想想，从整篇文档的第一个字符开始比较发现不匹配之后，其实匹配的过程中已经留下信息了，但是暴力算法没有有效利用或者维护起这种信息来导致复杂度过高. 因此KMP算法诞生——三位大神发明的. 以其首字母命名此算法为KMP。

分析

在讲述KMP算法之前，我们先来看幅图

​ 图1

可以看到, 上方的长方格是文档（text），下面的短方格是匹配串（pattern）, 在匹配的过程中，发生了不匹配（b!=c）, 那么如果是暴力算法的话，肯定就是将pattern的第一个a移动到text的b，两者对齐之后再进行重新匹配咯~ 这相当于将text已经移动到了c的指针又拉了回来（拉回到了b）!!! 这其实就是为什么BF算法效率那么低的原因了. 因为这相当于是完全抛弃了前面比较得到的信息!!!

那么问题来了——所谓高效的算法应该是什么?

应该是text上的指针永不后退的算法!!! 即text上的指针只会不断的后移动, 而不会出现明明已经移动到了c还要拉回b的情况~ kmp就是这样的算法.

那么问题来了，kmp是怎么做到text上的指针永不后退的呢?

首先要问——真的有必要让text的指针后退么? 再来看一幅图.

​ 图2

上图中，画的比图1抽象，但是能说明思想. 如图2所示，发生了失配事件. 但是至少说明前面一大段都是完全匹配的.

那么问题来了， 这一大段完全匹配这一点事实，不能好好利用吗? 再来看一幅图

​ 图3

如图3所示，A和B失配，如果pattern中存在一个C格子，使得C前的段L和A前的段M完全一致的话，则我们就可以不让指向text的A格子的指针回退, 而只需要将pattern的C和A对齐进行比较即可（因为L和M完全匹配）. 也就是这样

​ 图4

但是这样有没有可能会漏掉匹配情况呢? 也就是上图4中，pattern不需要移动到C，而是移动到C和B之间的某个格子就可以和A进行匹配了，也就是像下面这个样子

如果这样的话, 则会出现一段比L更长的L1出现. 因此，我们就不难知道，为了保证不漏掉任何匹配，我们需要保证

图3中L长度的最大性. 而回顾图3，我们知道L和M一样等价于L和N一样（这就利用到了失配之前的全部匹配这一点）.

注意，这里我们来到了一个非常tricky 的境地——我们已经将原本和text有关的性质化归到了仅仅与pattern有关的性质了.

这就是KMP算法的伟大之处. 根据上面的讨论，我们定义KMP算法中最核心的next数组

1
next[j]=k 的含义是如果在patternt[j]失配的话, 我们要跳到pattern[k]继续与text进行匹配, 1<=j<=strlen(pattern)+1.

什么意思? 就是如果匹配到了text[i]了（图3中的A），但是pattern[j](即图3中的B)和text[i]不相等. 那么pattern要跳到pattern[next[j]]（就是图3中的C）继续试探与text[i]等不等? 注意，有可能等，也可能不等哦~

比BF厉害的地方在于kmp就不需要text上的索引i回退了. 所以kmp很高效.

wait,wait,wait~ 为什么需要知道 next[strlen(pattern)+1]的值? 这是为了处理如果匹配成功之后pattern应该跳到pattern的哪个索引和text[i]继续匹配.

好了，那么next数组的严格数学定义是什么呢?

  1. next[0] 不用于存储数据

  2. next[1] = 0, 表示如果在pattern[1]就失配了，则要跳转到pattern的哪个索引继续进行匹配. 这里规定为0，目的是使得pattern和text都往后移动一格，这个是用于算法中特定的判断的，并没有什么实际的含义，因为pattern也好，text也好，next也好，他们的0索引都是不用于存储数据的. 下面简称pattern为p.

  3. 对于j>1, next[j] = max{1<=k \< j | p1,…,p_{k-1}=p_{j-k+1},..,p_{j-1}}, 注意，集合非空，因为k=1至少是符合条件的, 即 next[j] >= 1，注意，显然，next数组有性质—— next[j]<j, 注意, 我们显然不能允许k为j, 不然的话，p1,…,p_{k-1}=p_{j-k+1},..,p_{j-1}是平凡的，那么所有的next[j]就等于j了.这不是我们想要的.

于是如果有了next数组的话(完全根据pattern进行制作), 则不难可以写出kmp算法的，具体见下面的实现.

那么问题来了——最后的问题，next数组如何制作? 如果pattern 比较短小的话，则直接使用BF暴算，但是如果pattern很长的话，则O(M^2)的复杂度也是我们比较不能接受的.

所以我们需要推导——使用dp的思想——如果我们已经得到了 next[j]=k, 那么next[j+1]等于多少?

情形1. 如果 pattern[k]=pattern[j]的话，则因为next[j]=k, 所以根据k的最大性，我们知道pattern[j+1]=k+1

情形2. 如果pattern[k]!=pattern[j]的话, 则根据定义，我们需要找最大的s(1<=s<j+1，其实1<=s<k+1)使得

1
p1,...,p_{s-1}=p_{j-s+2},...,pj

​ 式1

根据式1以及p[k]!=p[j],我们知道s<k+1（s不能大于k+1是显然的，因为next[j]=k,next[j+1]最多增加1，即next[j+1]=s<=next[j]+1=k+1<j+1），但是我们已经知道next[j]=k了，即

1
p1,...,p_{k-1}=p_{j-k+1},...,p_{j-1}

​ 式2

而式1的必要条件是

1
p1,..,p_{s-2}=p_{j-s+2},...,p_{j-1}

​ 式3

根据式2的右边以及 s<k+1，我们知道式3的右边等于

1
式3的右边=p_{k-s+2},...,p_{k-1}

​ 式4

其中式4的右边是式2的左边的一部分. 所以式1的必要条件由式3进一步化为

1
p1...,p_{s-2}=p_{k-s+2},...,p_{k-1}

​ 式5

这就有意思了. 根据式5，以及next[k]的定义我们知道 s-1<=next[k]. 即式1的最大的那个s一定满足s-1<=next[k].

而因为式1中我们要求的是最大的s, 所以自然好奇的想问一下:

1
p1,...,p_{next[k]} 与 p_{j-(next[k]+1)+2},...,pj等不等?

​ 式6

结合既有的式2以及next[k]<k，我们知道其实

1
p1,...,p_{next[k]-1}和p_{j-next[k]+1},...,p_{j-1}相等

​ 式7

是成立的. 所以式6是否相等等价于

1
p_{next[k]}和pj相等

​ 式8

如果p_{next[k]}=pj的话，则next[j+1]=s=next[k]+1，就求出next[j+1]来了. 如果不等. 则需要继续化归.

那么怎么化归呢? 这个时候要走点意识流了（其实是懒得进行数学推导了，因为个人比较偏向于直观理解算法），看下图（根据next数组的定义，段1和段11，段2和段22，段3和段33分别全等，段3是段11的子集，段3是段22的子集）

正因为p[next[k]]和p[j]不相等，所以s=next[j+1]才不能开心的接受等于next[k]+1的结果. 所以我们要继续往前找, 那么找哪个合适呢? 换言之——哪个才是有潜力，可能成为候选者的呢（即所谓的必要条件）.

显然，我们需要上图中的”?” 满足它前面的段33和段3一致才行，这样的话，段33是段22的后半部分，进而是段2的后半部分，进而是段11的后半部分，进而是段1的后半部分. 而如果”？”和p[j]相等的话，则next[j+1]就等于”?”所在索引+1. 而看到段33和段3之间的关系——眼熟吗? 因为考虑到求next[j+1]的最大性，所以”?”要等于next[next[k]]才行. 所以就知道，我们只需要考察不断的next下去

最后基于上述详尽分析，我们给出以下用c/c++实现

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
#include "stdafx.h"
#include <iostream>
#include <cstring>
using namespace std;
#define LOCAL

const int MAX_N = 255;

char text[MAX_N], p[MAX_N]; // text是文档, p是待搜索的字符串，索引0都不用于存储数据,0索引用于存储字符串的长度(这属于Pascal语言对于字符串的处理)
int pnext[MAX_N]; //p的next数组,0索引不用于存储数据

void makenext() // 制作p的next数组 pnext
{
	pnext[1] = 0;
	for (int j = 2; j<= p[0]+1;j++)
	{
		int k = pnext[j-1];
		while(k&&p[j-1]!=p[k])k = pnext[k];
		pnext[j] = k+1;
	}
}

void kmp() // 在text中查找p
{
	int i = 1, j=1; // text和p 都从索引1开始匹配
	while(i<=text[0]) // 永不退后的text指针-i
	{
		while (text[i] == p[j] && j<=p[0] && i<=text[0])
		{
			i++;
			j++;
		}
		if (j==1) // 如果是在p的第一位就失配了, 则text后移一位继续与p[1]进行匹配
		{
			i++;
		}
		else
		{
			if (j>p[0]) // 如果完成了一次匹配（而导致适配）
			{
				printf("发现一次匹配, 位于文档的%d索引处.\n", i-p[0]); // 这里完全可以对匹配次数做统计
			}
			j = pnext[j];
		}
	}
}



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	puts("输入文本");
	scanf("%s", text+1);
	text[0] = strlen(text+1);
	puts("输入待匹配字符串");
	scanf("%s", p+1);
	p[0] = strlen(p+1);
	makenext();
	kmp();
	return 0;
}
/*
测试数据
GooglGoogle
Google
*/

上面的算法并没有抄网上的板子，而是按照我之前的分析自己写出来的.

kmp算法，当时在学严奶奶的书的时候觉得kmp是辣么的怪，但是如果像这里分析的那样——一切定义都是辣么的自然.

哦对了，忘了说KMP算法的复杂度是O(N+M).