串的模式匹配之KMP算法实现

概述

函数刻画

主串位置不变,next值就是模式串(子串)比较后应跳转的位置

不同位置

next[j]函数

next由模式串决定,看模式串当前比较位的前串中前后缀相同的个数来得k-1的值,next[当前位]=k+1

小补充

PM值:也称部分匹配值,每一位字符及其之前的字符所能匹配(前后缀相等的字符个数)的最大值。右移位数=当前比较的字符位置-对应的PM值,当PM=0时,右移位数最大。

next数组:是由每位字符对应的PM值右移一位(低位补-1)得到的结果

next数组的值:即当前所求next[j]数组,它是由所有next数组对应值+1修正得到的结果

一般题目需要求的话,最好倒推求:即求next数组的值——>next数组

代码实现

优化next函数

nextval数组

1.将当前字符与其next值对应的字符进行比较,如果不同,则当前字符的nextval与当前字符的next值保持一致

2.如果当前字符与其next值对应的字符相同,再比较next字符与其对应的next的字符进行比较,如果不同,则当前字符的nextval就与其next值对应字符的nextval值相同;否则如果当前字符的next字符与next字符对应的next的字符相同,当前字符的nextval就与其next值对应字符的next值对应的字符的nextval值相同......依次比较

总之,比较后与谁相同,nextval就与谁对应的next值相同,否则与当前比较字符的next值相同

代码实现

区别

代码整合

//串的应用
#define maxsize 100;//类型定义 
typedef struct {//顺序串=串数组+串长 char ch[maxsize+1];//下标从1开始存串 int length; 
}sstring;sstring s;//顺序串 
//串的模式匹配-KMP算法实现//求next数组:
void getnext(sstring t,int next[]){//通过模式串求得next数组的值int i=1;//标记当前比较位置 int j=0; //记录跳转位置 next[1]=0;while(i<t.length){//下标位置合法 :????为啥不能取等号 if(j==0||t.ch[i]==t.ch[j]){//字符匹配 或 开始匹配(因为next[0]位置是不用的,next数组是从1开始存储) ++i;++j;//比较下一个 next[i]=j;//记录当前next的值 }else  j=next[j];// 失配跳转} 
}
//匹配算法 
int KMP(sstring s,sstring t,int next[]){int i=1;//标记主串位置下标int j=1;//标记子串位置下标while(i<=s.length&&j<=t.length){if(j==0||s.ch[i]==t.ch[j]){//字符匹配或第一个字符就失配,指针下移 ++i;++j;}else j=next[j];//不匹配时,子串跳转,主串不变 } if(j>t.length)return i-t.length;//匹配成功,返回首字符在主串中的下标位置 else return 0; 
}//求nextval数组:与求next数组大致相同,只不过需要内嵌多一次比较
void getnextval(sstring t,int nextval[]){int i=1;//记录当前位置int j=0;//记录跳转位置nextval[1]=0; while(i<t.length){if(j==0||t.ch[i]==t.ch[j]){ //字符匹配 或 开始匹配(因为next[0]位置是不用的,next数组是从1开始存储) ++i;++j;//下标后移 //记录当前nextval值 if(t.ch[i]!=t.ch[j]) //后移位置字符不相等nextval[i]=j;//与next值保持一致else nextval[i]=nextval[j];//与相同字符的nextval值保持一致 }else j=nextval[j];//失配跳转}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3017933.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【知识碎片】2024_05_07

今天记录了两个代码和C的几个破碎知识。 第一段代码是基础型的&#xff0c;关于数组。第二段代码是二分的&#xff0c;一开始没通过全部案例&#xff0c;值得再看。 每日代码 1.记负均正 输入一个数组&#xff0c;输出负数的个数&#xff0c;整数的平均值&#xff08;0都不参…

C++:week2:C语言中高级

文章目录 (八) 指针0.概念1.指针基础(1)指针的声明(2)指针的两个基本操作①取地址运算符 &②解引用运算符 * (3)野指针①野指针②空指针③指针变量的赋值 vs 指针变量指向对象的赋值 (4)指针的应用①指针作为参数进行传递②指针作为返回值③拓展&#xff1a;栈帧 (5)常量指…

怎么将pdf的文件内容保存到mysql数据库中?

要将PDF导入到MYSQL&#xff0c;首先一步就是要先将PDF内容结构化&#xff0c;如果其内容为非结构化&#xff0c;则导入MYSQL的意义不大&#xff0c;具体操作方法如下&#xff1a; 将PDF文件的内容保存到MySQL数据库中通常涉及几个步骤。PDF文件包含的是格式化文本、图像和其他…

【记录】Python3| 将 PDF 转换成 HTML/XML(✅⭐PyMuPDF+tqdm)

本文将会被汇总至 【记录】Python3&#xff5c;2024年 PDF 转 XML 或 HTML 的第三方库的使用方式、测评过程以及对比结果&#xff08;汇总&#xff09;&#xff0c;更多其他工具请访问该文章查看。 文章目录 PyMuPDF 使用体验与评估1 安装指南2 测试代码3 测试结果3.1 转 HTML …

20240507 ubuntu20.04+ros noetic 跑通lioslam

任务&#xff1a;跑通lioslam 主要参考博客 IMU激光雷达融合使用LIO-SAM建图学习笔记——详细、长文、多图、全流程_ubuntu_AIDE回归线-GitCode 开源社区 (csdn.net) 1.不要用这一句 wget -O ~/Downloads/gtsam.zip https://github.com/borglab/gtsam/archive/4.0.0-alpha2…

华为eNSP中型企业局域网网络规划设计(下)

→b站传送门&#xff0c;感谢大佬← →华为eNSP中型企业局域网网络规划设计&#xff08;上&#xff09;← →拓扑图传送门&#xff0c;可以自己配置着玩← 配置ospf AR3 [AR3]ospf 1 router-id 3.3.3.3 //出口默认路由 [AR3-ospf-1]default-route-advertise always #area…

DeepSeek发布全新开源大模型,GPT-4级别能力 价格仅百分之一

最新国产开源MoE大模型&#xff0c;刚刚亮相就火了。 DeepSeek-V2性能达GPT-4级别&#xff0c;但开源、可免费商用、API价格仅为GPT-4-Turbo的百分之一。 因此一经发布&#xff0c;立马引发不小讨论。 从公布的性能指标来看&#xff0c;DeepSeek-V2的中文综合能力超越一众开源…

Redis是什么? 日常运维 Redis 需要注意什么 ? 怎么降低Redis 内存使用 节省内存?

你的项目或许已经使用 Redis 很长时间了&#xff0c;但在使用过程中&#xff0c;你可能还会或多或少地遇到以下问题&#xff1a; 我的 Redis 内存为什么增长这么快&#xff1f;为什么我的 Redis 操作延迟变大了&#xff1f;如何降低 Redis 故障发生的频率&#xff1f;日常运维…

25_Scala集合Tuple

文章目录 tuple1.元组定义2.Tuple元素访问3.如果元素的len2&#xff0c;称之为键值对对象&#xff0c;也称之为对偶元组4.补充上节Map5.Map集合遍历6.集合之间相互转化 tuple 概念&#xff1a;scala语言采用特殊的方式将无关的数据作为一个整体&#xff0c;组合在一起’ 1.元…

【数据结构】顺序表专题详解(带图解析)

最好的时光&#xff0c;在路上;最好的生活&#xff0c;在别处。独自上路去看看这个世界&#xff0c;你终将与最好的自己相遇。&#x1f493;&#x1f493;&#x1f493; 目录 •&#x1f319;说在前面 &#x1f34b;知识点一&#xff1a;什么是数据结构 • &#x1f330;1.什…

一览函数式编程

文章目录 一、 什么是函数式编程1.1 编程范式1.1.1 命令式编程(Imperative Programming)范式1.1.2 声明式编程(Declarative Programming)范式1.1.3 函数式编程(Functional Programming)范式1.1.4 面向对象编程(Object-Oriented Programming)范式1.1.5 元编程(Metaprogramming)范…

初始C++(一)

目录 前言&#xff1a; 命名空间&#xff1a; 总结&#xff1a; 前言&#xff1a; C语言学好了&#xff0c;现在当然要进阶了&#xff0c;那么就是从C开始。 C兼容C&#xff0c;支持其中90%的语法。可能有很多同学听说过C#&#xff0c;C#和C没有关系&#xff0c;是微软研究出…

☺☺☺☺☺☺☺栈的应用习题:有效的括号☺☺☺☺☺☺☺

目录 一解题思路&#xff1a; 二对解答代码分析&#xff1a; 三解答代码展示&#xff1a; 即浅学栈的创建后&#xff0c;可以简单利用其性质&#xff08;先进后出&#xff0c;后进先出&#xff09;来完成对一些题目的解答 如&#xff1a; 一解题思路&#xff1a; 这里我们可…

sql优化思路

sql的优化经验 这里解释一下SQL语句的优化的原理 1.指明字段名称&#xff0c;可以尽量使用覆盖索引&#xff0c;避免回表查询&#xff0c;因此可以提高效率 2.字面意思&#xff0c;无需过多赘述。索引就是为了提高查询效率的。 3.图中两条sql直接可以使用union all 或者 uni…

LeetCode 234.回文链表

题目描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为 回文链表 。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#xff1a; 输入&#xff…

Jmeter页面汉化和字体显示过小调整

在频繁解压使用Jmeter的时候&#xff0c;经常会遇到需要将页面的英文调整为中文&#xff0c;页面文字和编辑区域内容文字显示较小的问题&#xff0c;记录一下方便以后查阅。 1.页面汉化 Jmeter在解压启动之后页面显示是英文&#xff0c;如果需要修改为中文&#xff0c;可以修改…

STM32单片机ADC功能详解

文章目录 1. ADC概述 2. ADC结构图 3. 引脚定义 4. 转换模式 5. 数据对齐 6. 转换时间 7. 硬件电路 8. STM32使用ADC单/多通道检测数据 1. ADC概述 功能&#xff1a;ADC是一个将模拟信号&#xff08;如电压&#xff09;转换为数字信号的设备。在微控制器中&#xff0c…

我用 GitHub 9.8k 的 Go 语言 2D 游戏引擎写了个游戏

前言 hi&#xff0c;大家好&#xff0c;这里是白泽。今天给大家分享一个 GitHub &#x1f31f;9.8k 的 Go 语言 2D 游戏引擎。 https://github.com/hajimehoshi/ebiten 引擎的贡献者依旧在积极维护&#xff0c;是一个兼具学习 & 娱乐的项目&#xff01; 为此我也用这个…

vue组件传参数

在使用vue3进行开发的时候&#xff0c;我们一定绕不开的一个技术栈&#xff0c;就是组件传参。接下来我将介绍在vue3中如何运用这项技术。 在组件传参数中&#xff0c;分为两类&#xff0c;父传子参&#xff0c;或子传父参。需要了解的两个方法就是defineProps和defineEmits。…

顺序表的实现(迈入数据结构的大门)

什么是数据结构 数据结构是由&#xff1a;“数据”与“结构”两部分组成 数据与结构 数据&#xff1a;如我们所看见的广告、图片、视频等&#xff0c;常见的数值&#xff0c;教务系统里的&#xff08;姓名、性别、学号、学历等等&#xff09;&#xff1b; 结构&#xff1a;当…