当前位置: 首页 > news >正文

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:

google
next[0]next[1]next[2]next[3]next[4]next[5]next[6]
011121

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];
}

例如,对以下字符串:

ababba
next[0]next[1]next[2]next[3]next[4]next[5]next[6]
next数组011234
nextval数组010104

四. 案例实现

对于病毒检测:患病时,患者的DNA中包含病毒的DNA。但是病毒的DNA是环状的,也就是说假如aab是病毒的DNA,则aba,baa都是病毒的DNA。如图:

算法的主要思想如下:

  • 对于每一个待检测的任务,假设病毒DNA序列的长度是m,因为病毒DNA序列是环状的,为了线性取到每个可行的长度为m的模式串,可将存储病毒DNA序列的字符串长度扩大为2m,将病毒DNA序列连续存储两次。
  • 然后循环m次,依次取得每个长度为m的环状字符串,将此字符串作为模式串,将人的DNA序列作为主串,调用BF算法进行模式匹配。
  • 只要匹配成功,即可中止循环,表明该人感染了对应的病毒;否则,循环m次结束循环时,可通过BF算法的返回值判断该人是否感染了对应的病毒。
     

相关文章:

12.串,串的存储结构与模式匹配算法

目录 一. 一些术语 二. 串的类型定义 &#xff08;1&#xff09;串的顺序存储结构 &#xff08;2&#xff09;串的链式存储结构 三. 串的模式匹配算法 &#xff08;1&#xff09;BF算法 &#xff08;2&#xff09;KMP算法 四. 案例实现 串(String)---零个或多个任意字符…...

Ribbon:listOfServers ,${variableName:defaultValue}

解释&#xff1a; 配置了address的地址,请求会走address&#xff0c;也就是http://127.0.0.1:8081&#xff0c;通常用户与别的后端服务进行联调设置为其本地服务的ip。 如果address的地址被注释掉&#xff0c;如下面所示&#xff0c;类似这样的占位符${variableName:defaultVa…...

TensorFlow二元-多类-多标签分类示例

探索不同类型的分类模型&#xff0c;使用 TensorFlow 构建二元、多类和多标签分类器。 二元分类 简述 逻辑回归 二元交叉熵 二元分类架构 案例&#xff1a;逻辑回归预测获胜团队 多类分类 简述 Softmax 函数 分类交叉熵 多类分类架构 案例&#xff1a;预测航天飞机…...

【回眸】牛客网刷刷刷!(七)——通信协议之 网络通讯

目录 前言 1、TCP/IP分层模型 2、ARP缓存 3、TCP 协议之所以提供可靠传输&#xff0c;不怕丢包、乱序的主要的原因是 4、以太网数据链路层MII/GMII/RMII/RGMII四种常用接口 5、在以太网通信协议LWIP中&#xff0c;数据包管理机构采用数据结构pbuf 分类包括 6、关于以太网…...

MySQL 安装配置

MySQL 安装配置 MySQL 是最流行的关系型数据库管理系统,由瑞典MySQL AB公司开发,目前属于Oracle公司。 MySQL所使用的SQL语言是用于访问数据库的最常用标准化语言。 MySQL由于其体积小、速度快、总体拥有成本低,尤其是开放源码这一特点,一般中小型网站的开发都选择MySQL…...

【0824作业】C++ 拷贝赋值函数、匿名对象、友元、常成员函数和常对象、运算符重载

一、思维导图 二、作业&#xff1a;实现关系运算符的重载 关系运算符重载 概念&#xff1a; 种类&#xff1a;>、>、< 、< 、 、!表达式&#xff1a;L#R (L表示左操作数&#xff0c;R表示有操作数&#xff0c;#表示运算符)左操作数&#xff1a;既可以是左值也可以…...

ubuntu 22.04 LTS openai triton 安装

第一种方法&#xff1a; pip install triton 第二种方法&#xff0c;安装最新的版本&#xff1a; pip install -U --index-url https://aiinfra.pkgs.visualstudio.com/PublicPackages/_packaging/Triton-Nightly/pypi/simple/ triton-nightly 第三种方法&#xff1a; git c…...

Android SDK 上手指南||第七章 Java应用程序编程

第七章 Java应用程序编程 如果大家已经对Java非常熟悉&#xff0c;那么不妨直接忽略这部分内容。如果大家的技巧还存在局限或者对Java这种语言只闻其名&#xff0c;那么本文将为各位解答很多在Android开发当中经常遇到的问题。需要注意的是&#xff0c;这篇文章并不能作为Java…...

Vue 框架如何获取数组中的值?

在Vue框架中&#xff0c;获取数组中的值可以通过以下几种方式实现&#xff1a; 1、使用数组索引&#xff1a; 可以使用数组的索引来获取特定位置的值。在Vue中&#xff0c;可以通过在模板中使用差值表达式或指令来获取数组中的值。例如&#xff1a; <div>{{ myArray[0]…...

如何成立一家音频芯片/算法设计公司

一 如何成立一家音频芯片设计公司&#xff1f; 要成立一家音频芯片设计公司&#xff0c;可以按照以下步骤进行&#xff1a; 市场调研&#xff1a;了解音频芯片市场的需求和竞争情况&#xff0c;确定目标客户和定位。 制定商业计划&#xff1a;根据市场调研的结果&#xff0…...

用docker-compose搭建LNMP

docker-compose搭建LNMP 一、compose 的部署1.Docker Compose 环境安装 二、编写Docker Compose1.准备依赖文件,配置nginx2.配置mysql3.配置php4.编写docker-compose.yml5.执行6.查看 一、compose 的部署 &#xff08;1&#xff09;公司在实际的生产环境中&#xff0c;需要使用…...

JavaScript:基本语法(变量与函数的定义与使用)

文章目录 script 标签srcdefer 延迟加载 基本语法定义变量 与 使用变量基本类型typeof 查看变量类型复合类型数组类型定义对象类型定义 函数定义函数使用函数 script 标签 src 和scc一样可以内嵌也可以外src外引。 一般是推荐外引。 <script src"idx.js">&l…...

树莓派4B上安装Gitlab

参考连接&#xff1a; 树莓派上使用 GitLab 搭建专业 Git 服务 | 树莓派实验室 gitlab reconfigure 卡住 ruby_block[wait for redis service socket] action run_芹菜学长的博客-CSDN博客 以及用到了讯飞星火 系统版本信息 1.进入 giblab安装页面gitlab/gitlab-ce - Instal…...

JVM 之字节码(.class)文件

本文中的内容参考B站尚硅谷宋红康JVM全套教程 你将获得&#xff1a; 1、掌握字节码文件的结构 2、掌握Java源代码如何在JVM中执行 3、掌握一些虚拟机指令 4、回答一些面试题 课程介绍 通过几个面试题初始字节码文件为什么学习class字节码文件什么是class字节码文件分析c…...

neo4j函数

1、断言函数 1all()判断是否一个断言适用于列表中的所有元素2all()判断是否一个断言至少适用于列表中的一个元素3none()如果断言不适用于列表中的任何元素&#xff0c;则返回true4single()如果断言刚好只适用于列表中的某一个元素&#xff0c;则返回true5exists()如果数据局库…...

wazuh初探系列一 : wazuh环境配置

目录 方法一&#xff1a;一体化部署 安装先决条件 第一步、安装所有必需的软件包 第二步、安装Elasticsearch 1、添加 Elastic Stack 存储库 安装 GPG 密钥&#xff1a; 添加存储库&#xff1a; 更新源&#xff1a; 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

本智慧养老中心管理系统是为了提高用户查阅信息的效率和管理人员管理信息的工作效率&#xff0c;可以快速存储大量数据&#xff0c;还有信息检索功能&#xff0c;这大大的满足了老人信息和管理员这两者的需求。操作简单易懂&#xff0c;合理分析各个模块的功能&#xff0c;尽可…...

高效PDF校对:释放高质量内容的力量

在数字化世界中&#xff0c;内容是王者。随着企业和个人越来越依赖数字文档进行沟通、分享和创新&#xff0c;我们在PDF中传递的内容的质量变得至关重要。在这里&#xff0c;我们将探索高效的PDF校对如何帮助您释放高质量内容的真正潜力。 超越仅仅是“正确” 当我们谈论PDF校…...

【Git游戏】提交的技巧

修改历史的提交 rebase 通过git rebase -i 将要修改的提交提到最前端&#xff0c; 然后修改&#xff0c;再通过git commit --amend提交该记录&#xff0c;最后通过git rebase -i 在替换会原始的位置 &#xff08;该过程中有可能会产生rebase confict&#xff09; cherry-pick …...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...