首页 > 其他分享 >扩展KMP (ex_KMP)

扩展KMP (ex_KMP)

时间:2024-09-02 19:03:53浏览次数:8  
标签:le int 扩展 len ex 数组 KMP size

一些约定:

  • 字符串下标从1开始
  • s[1,i]表示S的第一个到第i个字符组成的字符串

解决的题型:

给你两个字符串A,B(A.size()=n,B.size()=m),求p数组

p[i]表示最大的len使得A[i,i+len-1]=B[1,len]
即A的第i位与B前缀的最大匹配的长度

比如;

A:aaaabaa

B:aaaa

p数组就是{4 3 2 1 0 2 1}

算法实现

  1. 我们要先求一个关于B的z数组,一些定义:
  • z[i]表示最大的len使得B[1,len]=B[i,i+len-1],比如对于B:aabcaabd z[5]=3, 一开始z[1]=m

  • Z-box:表示一段区间,用两个变量l,r表示,它表示目前为止B中右端点最大的一个区间[l,r]满足,B[l,r]=B[1,r-l+1] (即这段区间与它等长度的前缀相同),一开始l=r=0,在循环求解z数组的过程中不断更新

知道了一些定义我们就来看z数组怎么求
假设我们已经得出z[1]~z[i-1]了要求z[i],且目前的Z-box=[l,r]

(1) \(l \le i \le r\) 如下图

(实际上如果\(i \le r\) , i一定满足\(l \le i \le r\) ,因为我们是用1~i-1去更新l的)

r’表示r-l+1,则B[1,r’]=B[l,r] (为了下面叙述方便,我们称r’为r的对应点) 相同颜色代表这段区间相同

我们再求出i的对应点i’=i-l+1,则B[i’,r’]=B[i,r]

假设z[i’]=len 则B[1,len]=B[i’,i’+len-1],现在有两种情况

  • \(len \le r-i+1\):此时\(B[1,len]=B[i’,i’+len-1]=B[i,i+len-1]\)
    则z[i]=len

  • 而如果 \(len>r-i+1\),如下图

我们无法确定绿色部分是否相同,因此不能直接把len赋给z[i],但我们可以保证z[i]>=r-i+1,r后面的部分暴力扫描即可

(2)\(i>r\) 同样也是暴力往后扫描即可

注意:每次求完z[i]后如果i+z[i]-1>r 则用i和i+z[i]-1更新l,r

求z数组的代码如下

	z[1]=m,l=0,r=0;
	for(int i=2;i<=m;i++)
	{
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(b[i+z[i]]==b[1+z[i]]) z[i]++; //如果i>r那这里z[i]一开始是0
		if(i+z[i]-1>r) r=i+z[i]-1,l=i; 
	}

2.求解p数组过程差不多
这里的[l,r]表示最大的一段区间满足a[l,r]=b[1,r-l+1]

一开始,l=0,r=0

外层循环i从1到n (这里p[1]不用赋初值)

(1) \(l \le i \le r\) , 令i’=i-l+1,r’=r-l+1,len=z[i']:

  • ① \(len \le r-i+1\),则B[1,len]=B[i’,i’+len-1]=A[i,i+len-1],所以p[i]=len

  • \(len>r-i+1\),超出部分暴力扫描

(2) \(i>r\),暴力扫描

记得更新l,r

求解p数组代码

	l=0,r=0;
	for(int i=1;i<=n;i++)
	{
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(a[i+p[i]]==b[1+p[i]]&&i+p[i]<=n&&1+p[i]<=m) p[i]++;   
			//注意这里要判断边界 
		if(i+p[i]-1>r) r=i+p[i]-1,l=i;
	}

最后放上一道板题

P5410 【模板】扩展 KMP/exKMP(Z 函数)

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
char a[N],b[N];
int n,m;
string s1,s2;
int z[N],p[N];
int l,r;
int ans1,ans2;
signed main()
{
	cin>>s1>>s2;
	n=s1.size(),m=s2.size();
	for(int i=1;i<=n;i++) a[i]=s1[i-1];
	for(int i=1;i<=m;i++) b[i]=s2[i-1];
	z[1]=m,l=0,r=0;
	for(int i=2;i<=m;i++){
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(b[i+z[i]]==b[1+z[i]]) z[i]++;
		if(i+z[i]-1>r) r=i+z[i]-1,l=i; 
	}
	for(int i=1;i<=m;i++){
		ans1^=(z[i]+1)*i;
	}
	l=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(a[i+p[i]]==b[1+p[i]]&&i+p[i]<=n&&1+p[i]<=m) p[i]++;   
			//注意这里要判断边界 
		if(i+p[i]-1>r) r=i+p[i]-1,l=i;
	}
	for(int i=1;i<=n;i++){
		ans2^=(p[i]+1)*i;
	}
	printf("%lld\n%lld\n",ans1,ans2);
	return 0;
}

本博客参考的网址:

[C++]洛谷:【模板】扩展 KMP(Z 函数) 算法详解

标签:le,int,扩展,len,ex,数组,KMP,size
From: https://www.cnblogs.com/FloatingLife/p/18393313

相关文章

  • 详解 ThreadPoolExecutor 的参数含义及源码执行流程?
    Java学习+面试指南:https://javaxiaobear.cn线程池是为了避免线程频繁的创建和销毁带来的性能消耗,而建立的一种池化技术,它是把已创建的线程放入“池”中,当有任务来临时就可以重用已有的线程,无需等待创建的过程,这样就可以有效提高程序的响应速度。但如果要说线程池的话一定离不开Th......
  • Spring扩展点系列-InstantiationAwareBeanPostProcessor
    文章目录简介测试一1、配置文件Bean注册2、单元测试方法3、测试类4、输出结果结论测试二1、测试类2、输出结果结论源码解析postProcessPropertiesCommonAnnotationBeanPostProcessorAnnotationInjectedBeanPostProcessor总结简介spring容器中Bean的生命周期内所......
  • Java 根据模板生成 PDF 文件 以及 excel 文件
    模板PDF的字段引入maven<!--iTextforgeneratingPDFfiles--><dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13.2</v......
  • delphi开发Excel用户定义函数
    在Delphi中开发Excel用户定义函数(User-DefinedFunction,UDF)通常涉及到以下几个关键步骤:1.**创建DLL文件**-使用Delphi编写一个动态链接库(DLL),其中包含要作为ExcelUDF的函数。函数必须遵循特定的签名规范,以便Excel能够识别和调用。示例UDF函数:```delphilibr......
  • ffmpeg错误Invalid audio stream. Exactly one MP3 audio stream is required. Could
    错误消息Invalidaudiostream.ExactlyoneMP3audiostreamisrequired.Couldnotwriteheaderforoutputfile#0(incorrectcodecparameters?):InvalidargumentErrorinitializingoutputstream0:0--OnlyAACstreamscanbemuxedbytheADTSmuxerCoul......
  • LongWriter-6k 数据集开发利用 AgentWrite:一种在LLM中将输出长度扩展到超过10,000字,同
    大语言模型(LLMs)的领域已经取得了巨大的进展,特别是在扩展其记忆容量以处理越来越多的上下文方面。现在这些模型可以处理超过100,000个标记的输入,使得它们能够执行高度复杂的任务,例如生成长篇文本、翻译大型文档和总结大量数据。然而,尽管在处理能力方面取得了这些进展,在生成等长......
  • 关于Plex转码失败,下载解码器失败的问题
    plex服务器版本:1.40.5.8854系统:qnap最近我在外地访问我的plex时,部分视频总是出现转码失败的问题,然后我看了下plex的日志Sep02,202411:48:50.338[140385089600312]ERROR-[NSB]Errorinbrowserhandleread:125(Operationcanceled)socket=-1Sep02,202411:48:50......
  • Prometheus Alertmanager如何配置externalURL和generatorURL?alermanager webhook
    目录【1】alertmanagerwebhook内容(1)alertmanager.yml配置(2)发送给webhook的内容为json串 在promethes和alertmanager启动的时候,都加上--web.external-url就可以了./prometheus--config.file=prometheus.yml--web.external-url=http://x.x.x.x:9090./alert......
  • 线上applicationExecutor启动bean未加载到问题
    SpringBootapplicationExecutor启动bean未加载到1.环境springboot3.x+flowable2.问题原因报错日志:明显的使用线程池的时候Bean加载问题,发现报错日志后再代码中搜索是否存在这个bean,最终发现并没有,这个bean是spring官方创建的,官方创建示例如图:当这个Executor......
  • ISO 26262中的失效率计算:SN 29500-3 Expected values for discrete semiconductors
    目录概要1基准条件下的失效率2失效率转换2.1失效率预测模型2.2电压应力系数2.2.1电压应力系数计算模型2.2.2电压应力系数计算2.3温度应力系数2.3.1温度应力系数计算模型2.3.2温度应力系数计算2.4漂移灵敏度系数3任务剖面应力系数4早期失效系数概......