首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >浅谈 KMP

浅谈 KMP

原创
作者头像
Clare613
发布2025-07-16 17:53:49
发布2025-07-16 17:53:49
23200
代码可运行
举报
文章被收录于专栏:KMPKMP
运行总次数:0
代码可运行

前言:

有人说 CCF 是 coin collect Federation (金币收集联会)。于是又说 KMP 是 kill my parents (杀掉我的父母)。好像有点阴森。。。话不多说,开始了。

何为 KMP:

KMP算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 $\operatorname{next()}$ 函数实现,函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 $\mathcal{O}(m+n)$。

实现方法:

我们可以发现,KMP 的题目哈希似乎也可以做出来。但是我们可以发现,哈希其实有很多无用功。我们看下图:\

可以发现,在 c 的时候失配(失去匹配)了,但是前面的都符合。如果是哈希,就会像这样匹配:\

很明显,第 $2,4$ 次是无用功,而 KMP 就是为了避免这种无用功。具体是怎么避免的,请往下看。\

我们可以看到上图标红的区域其实是相同的,而第一次符合的就可以与自己本身所对应的先提前比较,避免浪费时间来处理整个的。\

那么怎么处理呢?我们需要用一个 $nxt$ 数组,而我们需要判断的就是,在一个固定的子串中,最长前后缀长度就是可以避免的。\

比如说下图:\

我们可以看到这一个字符串 $S$ 所对应的 $nxt$ 数组的数值其实是逐步递增的,那么我们就能得到一个 $\operatorname{getnext}$ 函数,如下:

代码语言:cpp
代码运行次数:0
运行
复制
void Get_Next(string x){
	int i=0,j=-1;
	nxt[0]=-1;
	while(i<len2){
		if(j==-1||x[i]==x[j]){
			i++;
			j++;
			nxt[i]=j;
		}
		else{
			j=nxt[j];
		}
	}
}

看完后发现并不难,接下来再附上 KMP 那一段代码,主要是运用 $nxt$ 数组,其实想一想并不难。

代码语言:cpp
代码运行次数:0
运行
复制
void kmp(string x,string y){
	gn(y);
	int i=0,j=0,ans=0;
	while(i<len1){
		if(j==-1||x[i]==y[j]){
			i++;
			j++;
		}
		else{
			j=nxt[j];
		}
		if(j==len2){
			ans++;
			j=nxt[j];
		}
	}
}

例题:

本期例题较少,以理解为主。题单

P3375 【模板】KMP:

模板题,没得说。

代码语言:cpp
代码运行次数:0
运行
复制
#include<bits/stdc++.h>
using namespace std;
int len1,len2,nxt[1000005];
void gn(string x){
	nxt[0]=-1;
	int i=0,j=-1;
	while(i<len2){
		if(j==-1||x[i]==x[j]){
			i++;
			j++;
			nxt[i]=j;
		}
		else{
			j=nxt[j];
		}
	}
}
void kmp(string x,string y){
	gn(y);
	int i=0,j=0;
	while(i<len1){
		if(j==-1||x[i]==y[j]){
			i++;
			j++;
		}
		else{
			j=nxt[j];
		}
		if(j==len2){
			cout<<i-j+1<<"\n";
			j=nxt[j];
		}
	}
}
int main(){
	string x,y;
	cin>>x>>y;
	len1=x.size();
	len2=y.size();
	kmp(x,y);
	for(int i=1;i<=len2;i++){
		cout<<nxt[i]<<" ";
	}
	return 0;
}

P4824 USACO15FEB Censoring S:

用栈来维护 KMP 的操作,对于后退时不一定要全退,注意就好了。

代码语言:cpp
代码运行次数:0
运行
复制
#include<bits/stdc++.h>
using namespace std;
int len1,len2,nxt[1000005];
int st[1000005],top,ss[1000005];
void gn(string x){
	nxt[0]=-1;
	int i=0,j=-1;
	while(i<len2){
		if(j==-1||x[i]==x[j]){
			i++;
			j++;
			nxt[i]=j;
		}
		else{
			j=nxt[j];
		}
	}
}
void kmp(string x,string y){
	gn(y);
	int i=0,j=0;
	while(i<len1){
		if(j==-1||x[i]==y[j]){
			st[++top]=i;
			ss[i]=j;
			i++;
			j++;
		}
		else{
			j=nxt[j];
		}
		if(j==len2-1){
			top-=len2;
			j=ss[st[top]];
		}
	}
}
int main(){
	string x,y;
	cin>>x>>y;
	len1=x.size();
	len2=y.size();
	kmp(x,y);
	for(int i=1;i<=top;i++){
		cout<<x[st[i]];
	}
	return 0;
}

P3435 POI 2006 OKR-Periods of Words:

留做练习。

代码语言:cpp
代码运行次数:0
运行
复制
#include<bits/stdc++.h>
#define int long long
using namespace std;
int len1,len2,nxt[1000005];
void gn(string x){
	nxt[0]=-1;
	int i=0,j=-1;
	while(i<len2){
		if(j==-1||x[i]==x[j]){
			i++;
			j++;
			nxt[i]=j;
		}
		else{
			j=nxt[j];
		}
	}
}
signed main(){
	cin.tie(0)->sync_with_stdio(0); 
	cout.tie(0)->sync_with_stdio(0); 
	cin>>len2;
	string x;
	cin>>x;
	gn(x);
	int ans=0;
	for(int i=1;i<=len2;i++){
		int j=i;
		while(nxt[j]){
			j=nxt[j];
		}
		if(nxt[i]){
			nxt[i]=j;
		}
		ans+=i-j;
	}
	cout<<ans;
	return 0;
}

后话:

到此为止。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言:
  • 何为 KMP:
  • 实现方法:
  • 例题:
    • P3375 【模板】KMP:
    • P4824 USACO15FEB Censoring S:
    • P3435 POI 2006 OKR-Periods of Words:
  • 后话:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档