12.串,串的存储结构与模式匹配算法
目录
一. 一些术语
二. 串的类型定义
(1)串的顺序存储结构
(2)串的链式存储结构
三. 串的模式匹配算法
(1)BF算法
(2)KMP算法
四. 案例实现
串(String)---零个或多个任意字符组成的有限序列。
一. 一些术语
子串:串中任意个连续字符组成的子序列称为该串的子串
主串:包含子串的串相应地称为主串
字符位置:字符在序列中的序号为该字符在串中的位置
子串位置:子串第一个字符在主串中的位置
空格串:由一个或多个空格组成的串,与空串不同
例如:给定字符串a、b、c、d,a='BEI',b= 'JING',c='BEIJING',d='BEI JING'
它们的长度是: 3,4,7,8;
c的子串是:a,b;
d的子串是:a,b;
a在c中的位置是:1;a在d中的位置是:1;
b在c中的位置是:4;a在d中的位置是:5;
串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。
二. 串的类型定义
串的抽象数据类型定义:同线性表,只不过处理对象是字符。
ADT String{数据对象:D={ ai | ai ∈ElemSet, i=1,2..,n, n≥0 }数据关系:R1= { <ai-1, ai >| ai-1, ai∈D, i=2,...,n }基本操作:StrAssign (&T,chars) //串赋值StrCompare (S,T) //串比较StrLength (S) //求串长Concat(&T,S1,S2) //串连结Index(S,T,pos) //求子串的位置...还有其他操作...
}ADT String
与前面完全相同,串也可分为顺序串和链串。
(1)串的顺序存储结构
#define MAXLEN 255
typedef struct{char ch[MAXLEN+1]; //存储串的一维数组int length; //串的当前长度
}SString;
说明:实际存储时通常是char ch[MAXLEN+1],然后把第一个位置空出,这在处理一些问题时会简便一些。
(2)串的链式存储结构
和链表不同的是,我们可以在一个结点有多个数据元素,这种结点我们称之为块,可以显著提高存储密度。
# define CHUNKSIZE 80 //块的大小可自定义
typedef struct Chunk{char ch[CHUNKSIZE];struct Chunk *next;
}Chunk; //定义一个块的结点typedef struct{Chunk *head,*tail; //串的头指针和尾指针int curlen; //串的当前长度
}LString; //字符串的块链结构
三. 串的模式匹配算法
模式匹配算法的目的:确定主串中所含子串(模式串)第一次出现的位置 (定位)。针对模式匹配问题,我们有BF算法(Brute-Force, 又称古典的、经典的、朴素的、穷举的)和KMP算法(速度快),下面介绍这两种算法。
(1)BF算法
BF算法采用的基本思想是穷举法。将主串的第pos个字符和模式串的第一个字符比较。若相等,继续逐个比较后续字符;若不等,从主串S的下一字符起,重新与模式串T的第一个字符比较。例如,目标串的长度m=6,模式串的长度n=4。则先将目标串的1-4位与模式串对应1-4位逐个比较(i=1,j=1),然后起始位置加1,将目标串的2-5位与模式串对应1-4位逐个比较(i=2,j=1),最后将目标串的3-6位与模式串对应位逐个比较(i=3,j=1)。如果这时候还没有找到,则返回0,表示目标串中不存在对应的模式串。
这里还需要牵扯到一个回溯的问题:模式串T比较到第j位时发现匹配不成功,这个时候要进入下一轮匹配。模式串T中j直接置1(前面讲了,字符串第一个索引为0的位置空出来),那么目标串S中i应该置多少呢?上一轮匹配中模式串T从1到j位,往后挪了j-1步,所以目标串S中第一个被比较的字符所有是i-(j-1),然后现在我们要进入下一轮循环,从这个字符的下一个字符开始,因此回溯的位置应该是i-(j-1)+1=i-j+2。
当匹配成功时,模式串T中指针j指向的位置索引应该是1+T.length,最后一个元素的下一个元素为空,退出循环,在此之前所有字符都匹配成功。所以返回的索引值应该是此刻的i值减去模式串的长度i-T.length。
下面给出BE算法的代码描述:
int Index_BF(SString S, SString T, int pos){int i=pos, j=1; //从主串第pos位开始查找while (i<=S.length && j<=T.length) {if (S.ch[i]==T.ch[j]) {++i; ++j;} //本字符对应位置匹配成功,主串和子串依次匹配下一个字符else {i=i-j+2;j=1;} //本字符匹配不成功,主串、子串指针回溯重新开始下一次匹配}if (j>=T.length) return i-T.length; //这个时候在主串中找到了子串,返回匹配的第一个字符的下标 else return 0; //直到所有循环结束仍没有在主串中找到子串,模式匹配不成功
}
最后讨论算法的时间复杂度,如果主串S,子串T的长度为m,n,最多需要进行的循环次数是(m-n+1)次,每次比较n次,则最坏情况下的时间复杂度是O((m-n+1)*n)。若n<<m,可简化为O(mn)。
(2)KMP算法
此部分难度较大,建议看王道的视频动画演示,这里总结一下怎么求next数组和nextval数组:
4.2_2_KMP算法_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1b7411N798?p=36&vd_source=7bf292964a807d18168b0c665fed431cnext数组的求法(手算练习):
- next[1]都无脑写0,next[2]都无脑写1;
- 其他next:在不匹配的位置前,划一根美丽的分界线,模式串一步一步往后退,直到分界线之前“能对上”,或模式串完全跨过分界线为止。此时j指向哪儿,next数组值就是多少。
例如,对于字符串google:
g | o | o | g | l | e | |
next[0] | next[1] | next[2] | next[3] | next[4] | next[5] | next[6] |
0 | 1 | 1 | 1 | 2 | 1 |
KMP算法实际上就是改变了指针的回溯位置,主串中指针不回溯,子串中指针回溯的位置由next数组确定。next数组的作用就是:当子串的第j个字符失配时,从子串的第next[i]的继续往后匹配,而不一定非要从1开始。
nextval数组求解:
在此基础上进一步优化next数组,具体操作是,首先解出next数组,然后用以下步骤优化:
nextval [1]=0;
for (int j=2; j<=T.length; j++) {if (T.ch[next [j]]==T.ch[j])nextval[j]=nextval[next[j]];elsenextval[j]=next[j];
}
例如,对以下字符串:
a | b | a | b | b | a | |
next[0] | next[1] | next[2] | next[3] | next[4] | next[5] | next[6] |
next数组 | 0 | 1 | 1 | 2 | 3 | 4 |
nextval数组 | 0 | 1 | 0 | 1 | 0 | 4 |
四. 案例实现
对于病毒检测:患病时,患者的DNA中包含病毒的DNA。但是病毒的DNA是环状的,也就是说假如aab是病毒的DNA,则aba,baa都是病毒的DNA。如图:
算法的主要思想如下:
- 对于每一个待检测的任务,假设病毒DNA序列的长度是m,因为病毒DNA序列是环状的,为了线性取到每个可行的长度为m的模式串,可将存储病毒DNA序列的字符串长度扩大为2m,将病毒DNA序列连续存储两次。
- 然后循环m次,依次取得每个长度为m的环状字符串,将此字符串作为模式串,将人的DNA序列作为主串,调用BF算法进行模式匹配。
- 只要匹配成功,即可中止循环,表明该人感染了对应的病毒;否则,循环m次结束循环时,可通过BF算法的返回值判断该人是否感染了对应的病毒。
相关文章:
12.串,串的存储结构与模式匹配算法
目录 一. 一些术语 二. 串的类型定义 (1)串的顺序存储结构 (2)串的链式存储结构 三. 串的模式匹配算法 (1)BF算法 (2)KMP算法 四. 案例实现 串(String)---零个或多个任意字符…...
Ribbon:listOfServers ,${variableName:defaultValue}
解释: 配置了address的地址,请求会走address,也就是http://127.0.0.1:8081,通常用户与别的后端服务进行联调设置为其本地服务的ip。 如果address的地址被注释掉,如下面所示,类似这样的占位符${variableName:defaultVa…...
TensorFlow二元-多类-多标签分类示例
探索不同类型的分类模型,使用 TensorFlow 构建二元、多类和多标签分类器。 二元分类 简述 逻辑回归 二元交叉熵 二元分类架构 案例:逻辑回归预测获胜团队 多类分类 简述 Softmax 函数 分类交叉熵 多类分类架构 案例:预测航天飞机…...
【回眸】牛客网刷刷刷!(七)——通信协议之 网络通讯
目录 前言 1、TCP/IP分层模型 2、ARP缓存 3、TCP 协议之所以提供可靠传输,不怕丢包、乱序的主要的原因是 4、以太网数据链路层MII/GMII/RMII/RGMII四种常用接口 5、在以太网通信协议LWIP中,数据包管理机构采用数据结构pbuf 分类包括 6、关于以太网…...
MySQL 安装配置
MySQL 安装配置 MySQL 是最流行的关系型数据库管理系统,由瑞典MySQL AB公司开发,目前属于Oracle公司。 MySQL所使用的SQL语言是用于访问数据库的最常用标准化语言。 MySQL由于其体积小、速度快、总体拥有成本低,尤其是开放源码这一特点,一般中小型网站的开发都选择MySQL…...
【0824作业】C++ 拷贝赋值函数、匿名对象、友元、常成员函数和常对象、运算符重载
一、思维导图 二、作业:实现关系运算符的重载 关系运算符重载 概念: 种类:>、>、< 、< 、 、!表达式:L#R (L表示左操作数,R表示有操作数,#表示运算符)左操作数:既可以是左值也可以…...
ubuntu 22.04 LTS openai triton 安装
第一种方法: pip install triton 第二种方法,安装最新的版本: pip install -U --index-url https://aiinfra.pkgs.visualstudio.com/PublicPackages/_packaging/Triton-Nightly/pypi/simple/ triton-nightly 第三种方法: git c…...
Android SDK 上手指南||第七章 Java应用程序编程
第七章 Java应用程序编程 如果大家已经对Java非常熟悉,那么不妨直接忽略这部分内容。如果大家的技巧还存在局限或者对Java这种语言只闻其名,那么本文将为各位解答很多在Android开发当中经常遇到的问题。需要注意的是,这篇文章并不能作为Java…...
Vue 框架如何获取数组中的值?
在Vue框架中,获取数组中的值可以通过以下几种方式实现: 1、使用数组索引: 可以使用数组的索引来获取特定位置的值。在Vue中,可以通过在模板中使用差值表达式或指令来获取数组中的值。例如: <div>{{ myArray[0]…...
如何成立一家音频芯片/算法设计公司
一 如何成立一家音频芯片设计公司? 要成立一家音频芯片设计公司,可以按照以下步骤进行: 市场调研:了解音频芯片市场的需求和竞争情况,确定目标客户和定位。 制定商业计划:根据市场调研的结果࿰…...
用docker-compose搭建LNMP
docker-compose搭建LNMP 一、compose 的部署1.Docker Compose 环境安装 二、编写Docker Compose1.准备依赖文件,配置nginx2.配置mysql3.配置php4.编写docker-compose.yml5.执行6.查看 一、compose 的部署 (1)公司在实际的生产环境中,需要使用…...
JavaScript:基本语法(变量与函数的定义与使用)
文章目录 script 标签srcdefer 延迟加载 基本语法定义变量 与 使用变量基本类型typeof 查看变量类型复合类型数组类型定义对象类型定义 函数定义函数使用函数 script 标签 src 和scc一样可以内嵌也可以外src外引。 一般是推荐外引。 <script src"idx.js">&l…...
树莓派4B上安装Gitlab
参考连接: 树莓派上使用 GitLab 搭建专业 Git 服务 | 树莓派实验室 gitlab reconfigure 卡住 ruby_block[wait for redis service socket] action run_芹菜学长的博客-CSDN博客 以及用到了讯飞星火 系统版本信息 1.进入 giblab安装页面gitlab/gitlab-ce - Instal…...
JVM 之字节码(.class)文件
本文中的内容参考B站尚硅谷宋红康JVM全套教程 你将获得: 1、掌握字节码文件的结构 2、掌握Java源代码如何在JVM中执行 3、掌握一些虚拟机指令 4、回答一些面试题 课程介绍 通过几个面试题初始字节码文件为什么学习class字节码文件什么是class字节码文件分析c…...
neo4j函数
1、断言函数 1all()判断是否一个断言适用于列表中的所有元素2all()判断是否一个断言至少适用于列表中的一个元素3none()如果断言不适用于列表中的任何元素,则返回true4single()如果断言刚好只适用于列表中的某一个元素,则返回true5exists()如果数据局库…...
wazuh初探系列一 : wazuh环境配置
目录 方法一:一体化部署 安装先决条件 第一步、安装所有必需的软件包 第二步、安装Elasticsearch 1、添加 Elastic Stack 存储库 安装 GPG 密钥: 添加存储库: 更新源: 2、Elasticsearch安装和配置 安装 Elasticsearch 包…...
【2023】Spring Validation中@NotNull注解、@NotBlank注解介绍以及使用
【2023】Spring Validation中NotNull注解、NotBlank注解介绍以及使用 前言一、简介spring-validation框架的常用注解 二、代码实现添加依赖1、实体举例2、Controller层:3、统一异常处理4、结果返回验证通过返回验证失败返回 前言 平常我们在编写代码的时候总需要很多if判空&am…...
nodejs+vue养老院管理系统 u1yrv
本智慧养老中心管理系统是为了提高用户查阅信息的效率和管理人员管理信息的工作效率,可以快速存储大量数据,还有信息检索功能,这大大的满足了老人信息和管理员这两者的需求。操作简单易懂,合理分析各个模块的功能,尽可…...
高效PDF校对:释放高质量内容的力量
在数字化世界中,内容是王者。随着企业和个人越来越依赖数字文档进行沟通、分享和创新,我们在PDF中传递的内容的质量变得至关重要。在这里,我们将探索高效的PDF校对如何帮助您释放高质量内容的真正潜力。 超越仅仅是“正确” 当我们谈论PDF校…...
【Git游戏】提交的技巧
修改历史的提交 rebase 通过git rebase -i 将要修改的提交提到最前端, 然后修改,再通过git commit --amend提交该记录,最后通过git rebase -i 在替换会原始的位置 (该过程中有可能会产生rebase confict) cherry-pick …...
SQL注入读写文件
文章目录 条件利用SQL注入漏洞读取hosts文件查看文件读写权限安全选项允许导入导出读取hosts文件 利用SQL注入漏洞写入一句话木马,并用蚁剑连接webshell写入文件 条件 SQL注入有直接SQL注入,也有文件读写时的注入,后者的主要 目的在于获取web…...
stm32之12.如何使用printf打印输出
主函数增加这些代码即可实现printf打印输出 需要添加头文件 #include "stdio.h" --------------- 源码 struct __FILE { int handle; /* Add whatever you need here */ }; FILE __stdout; FILE __stdin; int fputc(int c, FILE *f) { /* 发送一个字节 */ …...
敏感挂载hotplug容器逃逸分析与复现
前言 分析 实验 echo /path/to/hotplug/script > /proc/sys/kernel/hotplug 直接挂载设备即可,虚拟机直接启动或者卸载一下声卡就行 参考 Linux uevent分析、用户接收uevent以及mdev分析 - ArnoldLu - 博客园 (cnblogs.com)...
RTThread学习有关的Keil的两个符号 $Sub$ $main 与 $Super$ $main
Keil的两个符号$Sub$ $与 $Super$ $是其做的打“补丁”功能 具体调用方法就是程序中包含有main函数,和 $Sub$ $main 、 $Super$ $main 两个符号 源码先放出来 /* re-define main function */ int $Sub$$main(void) {rtthread_startup();return 0; }/*** brief Thi…...
Python实现企业微信群告警
Python实现企业微信告警 1. 创建企业微信群机器人 1-1. 什么是企业微信群机器人? 企业微信群机器人是企业微信平台提供的一种功能,可以通过Webhook方式将消息发送到指定的企业微信群中。它可以用于自动化发送通知、告警等信息,实现监控和信…...
python基础教程:re模块用法详解
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 一、正则表达式的特殊字符介绍 正则表达式 👇 👇 👇 更多精彩机密、教程,尽在下方,赶紧点击了解吧~ 素材、视频教程、完整代码、插件安装教程我都准备好了&a…...
基于亚马逊云科技无服务器服务快速搭建电商平台——部署篇
受疫情影响消费者习惯发生改变,刺激了全球电商行业的快速发展。除了依托第三方电商平台将产品销售给消费者之外,企业通过品牌官网或者自有电商平台销售商品也是近几年电商领域快速发展的商业模式。独立站电商模式可以进行多方面、全渠道的互联网市场拓展…...
git介绍+集成到IDEA中+使用gitee
目录 git介绍 本地工作流程 IDEA集git 添加到暂存区 添加到本地仓库 gitee使用 添加到远程仓库 git介绍 git是一个开源的分布式版本控制工具,效率高。可以记录历史代码,多人代码共享 知识小点: 集中式版本控制:使用中央存…...
【java】【项目实战】[外卖四]分类管理业务开发
前言:公共字段自动填充实现,删除业务逻辑实现 一、公共字段自动填充 1.1 问题分析 1.2 代码实现 1.2.1 修改实体类Employee package com.runa.reggie.entity;import com.baomidou.mybatisplus.annotation.FieldFill; import com.baomidou.mybatisplus.…...
【Go 基础篇】Go语言包详解:模块化开发与代码复用
介绍 在Go语言中,包(Package) 是一种用于组织代码的机制,用于将相关的函数、类型和变量等组织在一起,以便于模块化开发和代码复用。包的使用能够使程序结构更加清晰、可维护性更高,同时也是Go语言强调的一…...
【业务功能篇82】微服务SpringCloud-ElasticSearch-Kibanan-docke安装-进阶实战
四、ElasticSearch进阶 https://www.elastic.co/guide/en/elasticsearch/reference/7.4/getting-started-search.html 1.ES中的检索方式 在ElasticSearch中支持两种检索方式 通过使用REST request URL 发送检索参数(uri检索参数)通过使用 REST request body 来发送检索参数…...
【工具】XML和JSON互相转换
1、JSON解析为XML function parseJSONToXML(json) {let xmlDoc document.implementation.createDocument(null, );function parseValue(value, parentElement) {if (Array.isArray(value)) {for (let item of value) {let arrayElement xmlDoc.createElement(parentElement.…...
前端面试:【浏览器与渲染引擎】Web APIs - DOM、XHR、Fetch、Canvas
嗨,亲爱的读者!当我们在浏览器中浏览网页时,我们常常会与各种Web API打交道。这些API允许我们与网页内容、服务器资源和图形进行交互。本文将深入探讨一些常见的Web API,包括DOM、XHR、Fetch和Canvas,以帮助你了解它们…...
编码基础一:侵入式链表
一、简介概述 1、普通链表数据结构 每个节点的next指针指向下一个节点的首地址。这样会有如下的限制: 一条链表上的所有节点的数据类型需要完全一致。对某条链表的操作如插入,删除等只能对这种类型的链表进行操作,如果链表的类型换了&#…...
深圳IT行业供需:蓬勃发展的科技中心
深圳作为中国的科技中心之一,IT行业在这座城市蓬勃发展。本文将探讨深圳IT行业的供需状况,包括就业机会、技能需求以及行业前景展望。 近年来,深圳IT行业迅速发展,成为全球科技创新的重要枢纽之一。随着大量的科技企业和初创公司在…...
LeetCode 面试题 02.01. 移除重复节点
文章目录 一、题目二、C# 题解 一、题目 编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。 点击此处跳转题目。 示例1: 输入:[1, 2, 3, 3, 2, 1] 输出:[1, 2, 3] 示例2: 输入:[1, 1, 1, 1, 2] 输出:[1, …...
【Java8特性】——Stream API
一、概述 <1> 是什么 是数据渠道,用于操作数据源(集合、数组等)所生成的元素序列。 Stream 不会存储数据Stream 不会改变数据源,相反,会返回一个持有结果的新Stream。Stream 操作是延迟执行的,这意…...
grep命令的用法
文章目录 前言一、使用说明二、应用举例 前言 grep 命令用于查找文件里符合条件的字符串。 一、使用说明 -r: 如果需要搜索目录中的文件内容, 需要进行递归操作, 必须指定该参数 -i: 对应要搜索的关键字, 忽略字符大小写的差别 -n: 在显示符合样式的那一行之前,标…...
【无标题】jenkins消息模板(飞书)
这里写目录标题 Jenkins 安装的插件 发送消息到飞书预览 1 (单Job)预览 2 (多Job,概览) Jenkins 安装的插件 插件名称作用Rebuilder Rebuilder。 官方地址:https://plugins.jenkins.io/rebuild 安装方式&a…...
2023年国赛 高教社杯数学建模思路 - 案例:随机森林
文章目录 1 什么是随机森林?2 随机深林构造流程3 随机森林的优缺点3.1 优点3.2 缺点 4 随机深林算法实现 建模资料 ## 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 什么是随机森林ÿ…...
element Collapse 折叠面板 绑定事件
1. 点击面板触发事件 change <el-collapse accordion v-model"activeNames" change"handleChange"><el-collapse-item title"一致性 Consistency"><div>与现实生活一致:与现实生活的流程、逻辑保持一致,…...
CSS :mix-blend-mode、aspect-ratio
mix-blend-mode 元素的内容应该与元素的直系父元素的内容和元素的背景如何混合。 mix-blend-mode: normal; // 正常mix-blend-mode: multiply; // 正片叠底mix-blend-mode: screen; // 滤色mix-blend-mode: overlay; // 叠加mix-blend-mode: darken; // 变暗mix-blend-mode: …...
Module not found: Error: Can‘t resolve ‘less-loader‘解决办法
前言: 主要是在自我提升方面,感觉自己做后端还是需要继续努力,争取炮筒前后端,作为一个全栈软阿金开发人员,所以还是需要努力下,找个方面,目前是计划学会Vue,这样后端有java和pytho…...
量化QAT QLoRA GPTQ
模型量化的思路可以分为PTQ(Post-Training Quantization,训练后量化)和QAT(Quantization Aware Training,在量化过程中进行梯度反传更新权重,例如QLoRA),GPTQ是一种PTQ的思路。 QAT…...
CentOS下查看 ssd 寿命
SSD写入量达到设计极限,颗粒擦写寿命耗尽后会导致磁盘写入速度非常缓慢,读取正常。 使用smartctl及raid卡管理软件查看硬盘smart信息可以发现Media_Wearout_Indicator值降为1,表明寿命完全耗尽。 涉及范围 所有SSD处理方案 查看SSD smart信…...
Node基础--npm相关内容
下面,我们一起来看看Node中的至关重要的一个知识点-----npm 1.npm概述 npm(Node Package Manager),CommonJS包规范是理论,npm是其中一种实践。 对于Node而言,NPM帮助其完成了第三方模块的发布、安装和依赖等。借助npm,Node与第三方模块之间形成了很好的一个 生态系统。(类…...
Python图片爬虫工具
不废话了,直接上代码: import re import os import requests import tqdmheader{User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.139 Safari/537.36}def getImg(url,idx,path):imgre…...
制造执行系统(MES)在汽车行业中的应用
汽车行业在不断发展中仍然面临一些挑战和痛点。以下是一些当前汽车行业可能面临的问题: 1.电动化和可持续性转型:汽车行业正逐渐向电动化和可持续性转型,但这需要投入大量资金和资源,包括电池技术、充电基础设施等,同时…...
Spring与Mybatis集成且Aop整合
目录 一、集成 1.1 集成的概述 1.2 集成的优点 1.3 代码示例 二、整合 2.1 整合概述 2.2 整合进行分页 一、集成 1.1 集成的概述 集成是指将不同的组件、部分或系统组合在一起,以形成一个整体功能完整的解决方案。它是通过连接、交互和协调组件之间的关系来实…...
【nonebot-plugin-mystool】快速安装使用nonebot-plugin-mystool
快速安装使用nonebot-plugin-mystool,以qq为主 前期准备:注册一个QQ号,python3.9以上的版本安装,go-cqhttp下载 用管理员模式打开powershell,并输入以下命令 #先排查是否有安装过的nonebot,若有则删除 pip uninstal…...