浅谈KMP算法

目录

算法由来（历史课）

问题引入

解法：

（1）暴力解法

（2）玄学解法

KMP算法：

开始前你必须知道的：

next数组：

思路：

代码：

KMP算法：

思路：

代码：

模板题：

KMP算法是一种快速的匹配字符子串位置的算法，其思想对于其他一些算法也有沿用

算法由来（历史课）

KMP算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，并且于1977年联合发表，

因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。

其中D.E.Knuth是《计算机程序设计艺术》的作者（神犇）

问题引入

由两个字符串，text和pattern，他们都是以0为其实下标存储的，现在请你编程求出pattern在text中最早出现的下标（开头位置的）

若没有出现，则输出-1

输入样例：

一共两行，分别表示text和pattern

ABACABB

AB

输出样例：

一行，表示出现的位置

解法：

（1）暴力解法

这是一种很朴素的配对，枚举text的下标，若该下标开始的子串与pattern相比相同，则输出当前指针的位置，否则让指针后移

相当于模拟pattern后移的过程

代码如下：

bool check(int pos)
{
    for(int i=pos,j=0;j<m;i++,j++)
        if(text[i]!=pattern[j])
            return false;
    return true;
}
void solve()
{
    //n表示text长度，m表示pattern长度
    int ans=-1;
    for(int i=0;i<n;i++)
        if(check(i))
            ans=i,break;
    cout<<ans<<endl;
}
           

时间复杂度：O(nm)不用说，数据稍微大一点就炸了

（2）玄学解法

请思考：能不能不移动pattern的位置就解决问题？

问题稍难，请认真思考10`15min!

盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯

盯盯盯———————————————————————————————思考线

盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯

KMP算法：

开始前你必须知道的：

我们可以将text称之为文本串，将pattern称之为模式串。

KMP算法是暴力解法的一种优化（吧）

现在定义一个next数组（为了节约时间以及防止关键字报错（我也不懂怎么回事），以后请写作ne或自己起名，本文将统一使用next为数组名）

使得next[i]为i下一步跳跃的下标

那么应该怎么跳跃呢？！

next数组：

（关于本小节的正确性，这里讲的可能不好，可以戳我理解一下）

思路：

对于一个pattern串，这当中有Ta的前缀和后缀，那么若暴力解法出现失配（即比较text[i]和pattern[j]不相等的时候），向前跳跃一个位置（失配位置的下标pos前一个，即pos-1，0~pos-1之中与text串公共部分的最长相等前后缀的起始位置）。

下面，让我们开始找前后缀~

情况一：

有的蒻蒻说了，那么我如下图的情况是不是就向后跳一个单位呢？

【字丑勿喷】

此处是在pos=4的位置失配，那么在4之前即0~3这一段子串中，最大相同前后缀是“ABAB”（一个字符串的最大前缀等于最大后缀等于它本身），那么这里就是不是真的不跳了？

再次观察，其实还有一个子前后缀是相同的：“AB”与“AB”。于是乎，这种情况就需要pattern跳跃至后缀“AB”的起始位置

我们用i、k模拟pattern的指针，其中k用于给next数组赋值（next[i]=k，不要搞反了）。

情况一：

在pattern[k+1]==pattern[i]的时候，

此时的k就可以向前进一个单位了；

情况二：

在pattern[k+1] != pattern[i]的时候（即下一个不同）

k就要移动至k应该跳跃的位置，向前回溯。

即k=next[k]。

注意next[k]是小于k的，无论k取任何值。

情况三：

如果以上情况都没有发生那么更新i的位置就是next[i]=k;

代码：

void get_next()
{
	next[0]=-1;//在0这个位置不存在任何最大前后缀（情况三）
	int k=-1;
	for(unsigned int i=1;i<pattern.size();i++)
	{
		while(k>-1 && pattern[k+1] != pattern[i])//情况二
			k=next[k];
		if(pattern[k+1]==pattern[i])//情况一
			k++;
		next[i]=k;
	}
}
           

KMP算法：

思路：

大体就已经和next数组的一样了，下面还是说几种情况。

（下面变量的含义与讲解next时含义一样）

情况一：

若k>-1，并且失配的时候，那么就需要向前跳跃至next所指示的位置

即k=next[k];

情况二：

当pattern[k + 1] == text[i]，

k就向后移动一个单位

情况三：

k已经移动至末端了，就输出位置

即i-pattern.size()+1

代码：

void kmp()
{
	int k=-1;
	for(unsigned int i=0;i<text.size();i++)
	{
		while(k>-1 && pattern[k+1]!=text[i])
			k=ne[k];
		if(pattern[k+1]==text[i])
			k++;
		if(k==pattern.size()-1)
		{
			return i-k;
		}
	}
	return -1;
}
           

模板题：

Luogu 3375

POJ 3461