Back to Posts

【转载】KMP学习笔记

Posted in OI

转自可爱的学妹Cansult

沙茶的 KMP不详解(代码)

kmp好啊! kmp刺激神经啊!

KMP可以以O(n+m)的复杂度解决字符串的匹配问题

在普通的字符串匹配中, B串一旦在某一位(比如说第i位)上与A不一样, 就需要从头开始匹配B串, 这样最坏的复杂度是O(nm)

优化的一般思想都是利用重复的信息, 我们发现, 既然B在第i位与A失配了, 那么其实B的前i-1位都是和A匹配的, 我们可以利用这个来优化

直接讲代码吧…xMinh说主要就是代码不懂…

代码是去年写的…那时候还似懂非懂来着…然后码风也比较…清新…

预处理

p[i]的意义: 在B的前i位, 最长的[前缀与后缀相等的长度], 也就是(b[0]~b[p[i]])=b[i-p[i]]~b[i-1]) (不要在意边界…大体意思懂了就好… = =)

n=strlen(a);
m=strlen(b);
p[0]=p[1]=0;
int j=0; // p[i]: (b[0] ~ b[p[i]]) = (b[i - p[i]] ~ b[i - 1])
for(int i=1;i<m;i++)
{
	j=p[i]; // 
	while(j&&b[j]!=b[i])	j=p[j];
	p[i+1]=(b[i]==b[j])?(j+1):0;
}

这个是什么意思呢…我们在预处理p[i]..但是怎么预处理呢…肯定不能直接暴力匹配…那就n^2了是不…

j=p[i]

预处理

上图中, 蓝色的部分是已经确定的 前缀 == 后缀 长度, 当前匹配的是绿色的部分, 后半部分的绿色点是i++后得到的 , 前面的绿色点是j=p[i]得到的

现在就是要匹配第i位和第j位, 如果能匹配成功当然好, 直接把p[i + 1] = p[i] + 1即可

while (j && b[j]!=b[i]) j=p[j]

失配: 预处理

如果匹配失败, 我们发现既然我们已经知道前j位的p, 也就是紫色的1部分和2部分相等, 而两个蓝色的部分是相等的, 所以2和3是相等的, 也就是

{1=2 && 2=3} ——> 1=3

所以我们惊喜的发现, 1和3其实是相等的, 没有必要再去匹配了…我们可以直接匹配第$j$位和第$i$位, 如果不匹配, 可以继续类似递归一样继续下去…

n=strlen(a);
m=strlen(b);
p[0]=p[1]=0;
int j=0; // p[i]: (b[0] ~ b[p[i]]) = (b[i - p[i]] ~ b[i - 1])
for(int i=1;i<m;i++)
{
	j=p[i]; // j是当前应该和i(也就是当前长度字符串结尾)匹配的位
	while(j&&b[j]!=b[i])	j=p[j]; // 类似递归的处理过程, 知道递归到最底层无法递归: j回到开头了
	p[i+1]=(b[i]==b[j])?(j+1):0;
}

↑再粘一遍加深一下印象

匹配

终于到了激动人心的匹配…

j=0;
for(int i=0;i<n;i++)
{
	while(j&&a[i]!=b[j])	j=p[j];
	if(b[j]==a[i])	j++;
	if(j==m)
	{
		printf("%d\n",i-m+2);
		j=p[j];
	}
}

while (j && a[i]=b[j]) j=p[j]

失配: 匹配中

当前在匹配绿色的1, 然后如果失配了…

我们发现

{1=3 && 2=3} ——> 1=2

于是我们又省了一堆匹配…直接从2的结尾开始匹配绿色的1就好了

j=p[j]

不得不说…xMinh跟我说不理解这个地方的时候还是挺吃惊的…这个的意思呢, 就是你kmp匹配, 不能光找出第一个匹配的串啊, 还得找出来后面那些是匹配的啊

其实这里就是把他当失配, 来尽快的找后一个可以匹配的串

也就是相当于两个串变成了下面这样:

失配: 假的

懂了?

例题

简单水题

#include<bits/stdc++.h>
#define MAXN 1000000+5
#define MAXM 1000+5
using namespace std;
char a[MAXN],b[MAXM];
int n,m;
int p[MAXM];
int main()
{
	scanf("%s",a);
	scanf("%s",b);
	n=strlen(a);
	m=strlen(b);
	p[0]=p[1]=0;
	int j=0; // p[i]: (b[0] ~ b[p[i]]) = (b[i - p[i]] ~ b[i - 1])
	for(int i=1;i<m;i++)
	{
		j=p[i]; // 
		while(j&&b[j]!=b[i])	j=p[j];
		p[i+1]=(b[i]==b[j])?(j+1):0;
	}
	/*for(int i=0;i<m;i++)
	{
		cout<<p[i]<<" ";
	}
	cout<<endl;*/
	j=0;
	for(int i=0;i<n;i++)
	{
		while(j&&a[i]!=b[j])	j=p[j];
		if(b[j]==a[i])	j++;
		if(j==m)
		{
			printf("%d\n",i-m+2);
			j=p[j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d ",p[i]);
	}
	return 0;
}

脑洞进阶

SYCstudio大佬blog的动图解释

Read Next

AC自动机学习笔记