KMP算法

KMP算法 KMP算法

kmp算法通常被用于查找某一字符串的子串位置的的问题中，也叫做串的模式匹配。

比如说主串为 1，2，5，2，2，5，4，3

模板串为 2，2，5

如果位置从0开始，那么字串的位置为3，返回3即可。kmp就是快速是实现这一 *** 作的算法。

以这题为例：831. KMP字符串 - AcWing题库

朴素算法实现：

首先我们看看朴素算法，朴素算法就是利用两层for循环对比主串和子串，这么做会TLE下边来看看代码，比较简单：

char p[N],s[N];

for(int i = 0;i < m;i++)//遍历主串
    for(int j = 0;i < n;i++)//指针每后移一位将子串与主串的部分进行对比
        if(s[i] != p[i])break;//如果不符合条件即退出内层的对比循环

当然，可以对朴素算法进行适当的优化，在读入主串每一位的时候就将这一位与子串的第一位进行对比，如果相等，就将下标存入一个数组。当然这种写法也是会TLE，代码如下：

char p[N],s[N];
int I[N];

cin >> n;
for (int i = 0; i < n; i++)//输入模板串
{
	cin >> c;
	p[i] = c;
}
cin >> m;
for (int i = 0; i < m; i++)//输入主串
{
	cin >> c;
	s[i] = c;
	if (c == p[0])I[idx++] = i;//如果这一位与子串的第一位相等，将其下表存入数组I
}
for (int i = 0; i < idx; i++)//读取I中的坐标
{
	flag = 1;
	for (int j = I[i], k = 0; k < n; k++, j++)
	{
		if (s[j] != p[k])flag = 0;
	}
	if (flag)cout << I[i] << ' ';
}

如何才能让它在时间内完成 *** 作呢？哎，下面来看看KMP算法

KMP算法

KMP算法的代码比较简洁，但是它的思想较为抽象，这里我们着重讲解思想。

先看看完整代码：

#include
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int n, m;
int ne[N];

int main()
{
	cin >> n >> p + 1 >> m >> s + 1;

	for (int i = 2, j = 0; i <= n; i++)//next数组的计算
	{
		while (j && p[i] != p[j + 1])j = ne[j];
		if (p[i] == p[j + 1])++j;
		ne[i] = j;
	}
    
	for (int i = 1, j = 0; i <= m; i++)//匹配
	{
		while (j && s[i] != p[j + 1])j = ne[j];
		if (s[i] == p[j + 1])++j;
		if (j == n)
		{
			printf("%d ", i - n);
			j = ne[j];
		}
	}
	return 0;
}

可以清晰得看到，代码中有两个for循环。它们分别用于求ne和匹配主串与模板串，记住它们的功能。

很简单难理解对吧，莫慌，让我们看看它的实现过程：

首先，除了主串和模板串，我们要再开一个int数组nent[N]（我这里用ne），这个数组的是储存模板串p下标用于跳转的。不理解没关系，我们接着往下看。我们假设主串为bacwacwaactiedc、模板串为acwaactle，当然，模板串是从1下标开始读入的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YR00PLdB-1642906890120)(E:笔记&诗歌散文笔记博客图片微信图片_20220122234206.png)]

先来看看匹配时的初始状况：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UkyPYEH9-1642906890122)(E:笔记&诗歌散文笔记博客图片微信图片_20220123100500.png)]

匹配时，i从1开始，j从0开始。

匹配s[i]与p[j+1]，能看到s[1]与p[0+1]并不相等，那么讲i移向下一位。

s[2]与p[0+1]相等，继续对比下一位，相等。一直到s[5]与p[3+1]不相等，这时候就让s[i]与p[ne[j]]对比

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GJNiS1lo-1642906890122)(E:笔记&诗歌散文笔记博客图片微信图片_20220123102323.png)]

ne[3]上存的值为0（至于为什么下边再讲），那么就是让s[5]与p[0]配对，其相对位置变成以下情况：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9X9rvBlV-1642906890123)(E:笔记&诗歌散文笔记博客图片微信图片_20220123102706.png)]

再匹配，发现符合，于是在j到达末尾时输出i-n，即子串的位置。

再就是它的next数组的计算过程。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tGag6e15-1642906890123)(E:笔记&诗歌散文笔记博客图片微信图片_20220122234206.png)]

让i从2开始，j从0开始，遍历对比p[i]与p[j+1]，如果相等，就将j右移，否则就回溯。

ip[i]jp[j+1]ne[i]2c0a03w0a04a0->1a15a1->0->1a->c->a16c1->2c->w27t2->0w->a08l0a09e0a0

可以看看下边这个网站中的动图加强理解：

kmp算法动图演示

color=“blue”>可以看看下边这个网站中的动图加强理解：

kmp算法动图演示