首页 > 其他分享 >KMP模式匹配 学习笔记

KMP模式匹配 学习笔记

时间:2022-10-11 21:13:54浏览次数:73  
标签:int 笔记 next nex KMP 字符串 include 模式匹配

功能

能在线性时间内判断字符串\(A[1~N]\)是否为字符串\(B[1~M]\)的子串,并求出字符串\(A\)在字符串\(B\)中各次出现的位置。

实现

1.对字符串\(A\)进行自我“匹配”,求出一个数组\(next\),其中\(next[i]\)表示“\(A\)中以\(i\)结尾的非前缀子串”与“\(A\)的前缀”能够匹配的最长长度。特别地,当不存在这样的\(j\)时,令\(next[i]=0\).由于\(next\)的对象是非前缀子串,所以\(next[1]=0\);

概念解释:字符串的前缀是指字符串的任意首部。比如字符串“\(abbc\)”的前缀有“\(a\)”,“\(ab\)”,“\(abb\)”,“\(abbc\)”。同样,字符串的任意尾部是字符串的后缀,“\(abbc\)”的后缀有“\(c\)”,“\(bc\)”,“\(bbc\)”,“\(abbc\)”。


\(next[i]=max{j},其中j<i并且A[i-j+1~i]=A[1~j]\)

2.对字符串\(A\)与\(B\)进行匹配,求出一个数组\(f\),其中\(f[i]\)表示“\(B\)中以\(i\)结尾的子串”与“\(A\)的前缀”能够匹配的最长长度。


\(f[i]=max{j},其中j<=i并且B[i-j+1~i]=A[1~j]\)

代码

KMP算法\(next\)数组的求法
1.初始化\(next[1]=j=0\),假设\(next[1~i-1]\)已求出,下面求解\(next[i]\).
2.不断尝试扩展匹配长度\(j\),如果扩展失败(下一个字符不相等),令\(j\)变为\(next[j]\),直至\(j\)为\(0\)(应该从头开始匹配)。
3.如果能够扩展成功,匹配长度\(j\)就增加\(1\).\(next[i]\)的值就是\(j\).

next[1]=0;
for(int i=2,j=0;i<=n;i++)
{
	while(j>0&&&a[i]!=a[j+1]) j=next[j];
	if(a[i]==a[j+1]) j++;
	next[i]=j;
}

KMP算法\(f\)数组的求法

for(int i=1,j=0;i<=m;i++)
{
	while(j>0&&(j==n||b[i]!=a[j+1])) j=next[j];
	if(b[i]==a[j+1]) j++;
	f[i]=j;
	//if(f[i]==n),此时就是A在B中的某一次出现 
}

例题

例题1:P3375 【模板】KMP字符串匹配

这道题完完全全就是对上述两个代码块的直接使用。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
#define M 1000010
char p[N],s[M];//p模式串 s主串 
int nex[N],f[N];
int ans;
using namespace std;
int main()
{
	cin>>s+1>>p+1;
	int lp=strlen(p+1);
	int ls=strlen(s+1);
	for(int i=2,j=0;i<=lp;i++)
	{
		while(j>0&&p[i]!=p[j+1]) j=nex[j];
		if(p[i]==p[j+1]) j++;
		nex[i]=j;
	}
	for(int i=1,j=0;i<=ls;i++)
	{
		while(j&&(j==lp||s[i]!=p[j+1])) j=nex[j];
		if(s[i]==p[j+1]) j++;
		f[i]=j;
		if(f[i]==lp)
		{
			ans=i-lp+1;
			printf("%d\n",ans);
		}
	}
	for(int i=1;i<=lp;i++) printf("%d ",nex[i]);
	return 0;
}

例题2




这道题引入了一个新概念:循环同构。

其实,判断两个串是否循环同构也可以利用上述的KMP算法。比如欲判断字符串\(A\)和\(B\)是否循环同构,我们只需要新定义一个字符串\(C\)为重复两遍的\(A\),就是说,若\(A=aab\),则\(C=aabaab\).然后用KMP判断\(C\)中是否有\(B\),若有,则\(A\)和\(B\)循环同构,反之则不循环同构。

具体到这道题,我们可以枚举所有因数,然后按因数分段,再用上述方法判断。一旦出现两段之间非循环同构就break,这样能节省不少时间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e6+10;
int t,n;
char a[N];
int nex[N],b[N],f[N];
void kmp(int x)
{
	nex[1]=0;
	for(int i=2,j=0;i<=x;i++)
	{
		while(j>0&&a[i]!=a[j+1]) j=nex[j];
		if(a[i]==a[j+1]) j++;
		nex[i]=j;
	}
}
bool judge()
{
	for(int i=2;i<n;i++)
	{
		if(n%i==0)
		{
			int x=i,p=1,w=n/x;
			bool kx=1;
			kmp(x);
			for(int j=1;j<=w-1;j++)
			{
				for(int k=x*j+1;k<=x*(j+1);k++)
					b[k-x*j]=b[k+x-x*j]=a[k];
				for(int k=1,w=0;k<=x*2;k++)
				{
					while(w>0&&(w==x||b[k]!=a[w+1])) w=nex[w];
					if(b[k]==a[w+1]) w++;
					f[k]=w;
					if(f[k]==x)
					{
						kx=1;
						p++;
						break;
					}
					kx=0;
				}
				if(!kx) break;
			}
			if(p==w) return 1;
		}
	}
	for(int j=1;j<n;j++)
		if(a[j]!=a[j+1])
			return 0;
	return 1;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%s",&n,a+1);
		if(n==1)
		{
			puts("No");
			continue;
		}
		if(judge()) puts("Yes");
		else puts("No");
	}
	return 0;
}

标签:int,笔记,next,nex,KMP,字符串,include,模式匹配
From: https://www.cnblogs.com/fish4174/p/16782558.html

相关文章

  • vue-router_学习笔记
    1.动态导入路由模块import{createRouter,createWebHashHistory,RouteRecordRaw}from"vue-router";//*导入所有routerconstmetaRouters=import.meta.glob(......
  • TensorFlow学习笔记
    TensorFlowCourse1andCourse2【吴恩达团队Tensorflow2.0实践系列课程第一课】TensorFlow2.0中基于TensorFlow2.0的人工智能、机器学习和深度学习简介及基础编程【吴......
  • CVPR2022 Oral OGM-GE阅读笔记
    标题:BalancedMultimodalLearningviaOn-the-flyGradientModulation(CVPR2022Oral)论文:https://arxiv.org/abs/2203.15332领域:多模态学习解决本质问题在某些多模态......
  • MyBatisPlus笔记
    MyBatisPlus快速入门1.创建数据库mybatisplus2.创建user表并插入数据DROPTABLEIFEXISTSuser;CREATETABLEuser(idBIGINT(20)NOTNULLCOMMENT'主键I......
  • Vision Transformer源码阅读笔记
    代码:首先阅读文件vit_model.pyVIT模型中输入图片的大小是固定的,所以如果大小不对,就要报错【函数中卷积核太大,能不能换成3x3的】【每一个patch都是同一组卷积核卷积得到......
  • 【学习笔记】Servlet
    ServletServlet简介servlet是sun公司开发动态web的一门技术sun公司在这些API中提供了一个接口叫做Sevlet如果你想开发一个Servlet程序,只需要:编写一个类,实现Se......
  • nginx笔记
    场景一:请求时header中参数带有下划线‘_’时Nginx转发后此类参数丢失。原因:nginx默认request的header中包含’_’时,会自动忽略掉。解决方案:1、header参数不使......
  • 《基于Apache Flink的流处理》读书笔记
            前段时间详细地阅读了《ApacheFlink的流处理》这本书,作者是FabianHueske&VasilikiKalavri,国内崔星灿翻译的,这本书非常详细、全面得介绍了Flink流处......
  • linux笔记_1_db2数据库创建初始化
    1、创建用户compgen-uuseraddbank_bl-d/home/bank_bl-gdb2iadm1passwdbank_bl2、进入实例用户su-db2inst13、数据库操作db2listdbdirectory(查看......
  • MyBatis-Plus个人笔记
    第一章MyBatis-Plus入门1)MP简介官方地址:http://mp.baomidou.com代码发布地址:Github:https://github.com/baomidou/mybatis-plusGitee:https://gitee.com/baomi......