A Huster

0%

KMP浅谈

Posted on Edited on Valine:

关于KMP

​ KMP其实是三个人名字的缩写,因为是他们同时发现的(大佬惹不起);

​ KMP作为CSP考点,主要亮点是其优秀的匹配复杂度,而且消耗空间小,比起hash虽然有些局限性,但是因为其正确率高,所以经常被人使用.

前置知识

​ 关于字符串的读取,以及字符串相关操作的基础了解,这里涉及字符串匹配以及子串;

入坑

​ 其实KMP并不困难,只是让人难受的是它比较抽象的数组跳跃,我想这个并不需要过多解释;

思想

​ KMP常用于一个字符串是否出现在另一个字符串中.我们知道,如果暴力匹配了话,每次失配时就必须重新开始(不能贪心地从失配位置匹配),这样造成很大的浪费,那么我们想从已经匹配过的字符串中提取一些信息,以至于让我们不跳那么远,那这怎么办?

​ KMP算法就由此诞生了,它通过记录模式串的内部信息,为匹配时提供信息,可以节省大量时间.

模版

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
#include<iostream>
#include<cstring>
#define maxn 1000007
using namespace std;
int t,nxt[maxn],l1,l2,ans;
char s1[maxn],s2[maxn];

void get_nxt(){
	int t;
	nxt[0]=-1;
	for(int i=1;i<l2;i++){
		t=nxt[i-1];
		while(s2[i]!=s2[t+1]&&t>=0) t=nxt[t];
		if(s2[t+1]==s2[i]) nxt[i]=t+1;
		else nxt[i]=-1;
	}
}

void KMP(){
	int i=0,j=0;
	while(i<l1){
		if(s1[i]==s2[j]){
			i++,j++;
			if(j==l2)
				ans++,j=nxt[j-1]+1;
		}else{
			if(j==0) i++;
			else j=nxt[j-1]+1;
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>s2>>s1;ans=0;
		l1=strlen(s1),l2=strlen(s2);
		memset(nxt,0,sizeof nxt);
		get_nxt();KMP();
		std::cout<<ans<<endl;
	}
	return 0;
}

关于next数组的几个性质

​ 因为next与stl冲突所以命名为nxt数组;

​ next数组有一些性质:

​ $next[l]$ 到 $l$ 为模式串的最小循环节,当然必须满足一个条件,即最小循环节长度是整个串长度的因数,如果不是了话,那么一定是开头的字符串有残余,而残余字符串为循环节的后缀;

​ 那么考虑一下,如果我们想要找最小循环节,直接初始化后,找 $next[l]$ 即可,当然还要判断一下;

​ 想象一下 $next$ 数组的跳跃,我们能找到什么?即从 $1$ ~ $next [ l ] $ 既是前缀又是后缀,那么我们可以找到子串中的最大前缀和后缀相同的;

匹配时需要注意的细节

​ 我们常常会遇到让我们求出循环次数,以及不重叠循环次数,其区别只是判断 $j==l2$ 时 $j$ 是否要跳回 $next[j]$ ;

​ 或者是直接判断是否有这个模式串,直接 $return$ 即可;

关于题目变形

​ 主要是应该看出匹配方式,以及字符串的重构问题;

TO BE CONTINUED
本站访问次数：