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

数据结构—串

4.1串

4.1.1串的定义

串(String)——零个或多个任意字符组成的有限序列

S="a1 a2...an"

串的定义——几个术语

  • 子串:串中任意个连续字符组成的子序列称为该串的子串

    例如,“abcde”的子串有:

    “ ”、“a”、“ab”、“abc”、“abcd” 和 “abcde”等

    真子串是指不包含自身的所有子串。

  • 主串:包含子串的串相应地称为主串。

  • 字符位置:字符在序列中的序号为该字符在串中的位置。

  • 子串位置子串第一个字符在主串中的位置。

  • 空格串:由一个或多个空格组成的串,与空串不同

串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。

如:“abcd” ≠ “abc”

​ “abcd” ≠ “abcde”

所有的空串是相等的。

4.1.2串的类型定义、存储结构及其运算

串中元素逻辑关系与线性表的相同,串可以采用与线性表相同的存储结构。

串的顺序存储结构

#define MAXSIZE 255
typedef struct {char ch[MAXSIZE + 1];//存储串的一维数组int length;//串的当前长度
}SString;

串的链式存储结构

可以将多个字符存放在一个结点中,以克服其缺点。

#define CHUNKSIZE 80//块的大小可由用户定义
typedef struct Chunk {char ch[CHUNKSIZE];struct Chunk* next;
}Chunk;
typedef struct {Chunk* head, * tail;//串的头指针和尾指针int curlen;//串的当前长度
}LString; //字符串的块链结构

4.1.3串的模式匹配算法

算法目的:

  • 确定主串中所含子串模式串第一次出现的位置(定位)。

算法应用:

  • 搜索引擎、拼写检查、语言翻译、数据压缩

算法种类:

  • BF算法(暴力破解法)
  • KMP算法
1、BF算法(重点)

Brute-Force简称为BF算法,亦称为简单匹配算法。采用穷举法的思路。

S: a a a a b c d 主串:正文串

T: a b c 子串:模式

算法思路:是从S的每一个字符开始依次与T的字符进行匹配。

匹配失败:i = i - j + 2 (回溯) j=1(从头开始)

匹配成功:i - t.length

index(S,T,pos)

  • 将主串的第pos个字符和模式串的第一个字符比较
    • 若相等,继续逐个比较后续字符;
    • 若不等,从主串的下一字符起,重新与模式串的第一个字符比较。
  • 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
  • 否则,匹配失败,返回值0。
int index_BF(SString S, SString T,int pos) {int i = pos, j = 1;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;//模式匹配不成功
}
2、KMP算法

该算法较BF算法有较大改进,从而使算法效率有了某种程度的提高。

利用已经部分匹配的结果而加快模式串的滑动速度。且主串S的指针i不必回溯。

为此,定义next[j]函数,表明当模式中第 j 个字符与主串中相应字符 ”失配“ 时,在模式中需重新和主串中的该字符进行比较的字符的位置,

KMP算法中next数组及nextval数组的计算(应付考试用)_c1er的博客-CSDN博客_nextval数组

j1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
模式串a b c a a b b c a b c a a b d a b
next[j]0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
void get_next(SString T, int& next[]) {int i = 1;next[1] = 0;int j = 0;while (i < T.length) {if (j == 0 || T.ch[i] == T.ch[j]) {++i;++j;next[i] = j;}else j = next[j];}
}
int index_KMP(SString S, SString T, int pos) {int i = pos;int j = 1;while (i < S.length && j < T.length) {if (j == 0 || S.ch[i] == T.ch[j]) {++i;++j;}else j = get_next[j];//i不变,j后退}if (j > T.length) return i - T.length;//匹配成功else return 0;//返回不匹配标志
}

相关文章:

数据结构—串

4.1串 4.1.1串的定义 串&#xff08;String&#xff09;——零个或多个任意字符组成的有限序列 S"a1 a2...an"串的定义——几个术语 子串&#xff1a;串中任意个连续字符组成的子序列称为该串的子串 例如&#xff0c;“abcde”的子串有&#xff1a; “ ”、“a”、…...

hive 全量表、增量表、快照表、切片表和拉链表

全量表&#xff1a;记录每天的所有的最新状态的数据&#xff0c;增量表&#xff1a;记录每天的新增数据&#xff0c;增量数据是上次导出之后的新数据。快照表&#xff1a;按日分区&#xff0c;记录截止数据日期的全量数据切片表&#xff1a;切片表根据基础表&#xff0c;往往只…...

数据结构07:查找[C++][B树Btree]

图源&#xff1a;文心一言 考研对于B树的要求重点在推理手算的部分&#xff0c;只参考王道论坛咸鱼老师的视频就可以了&#xff1b;若时间非常充裕的小伙伴&#xff0c;也可以往下滑了解一下代码~&#x1f95d;&#x1f95d; 备注&#xff1a; 这次的代码是从这里复制的&…...

在CSDN学Golang云原生(Kubernetes集群管理)

一&#xff0c;Node的隔离与恢复 在 Kubernetes 集群中&#xff0c;Node 的隔离与恢复通常可以通过以下方式实现&#xff1a; 使用 Taints 和 Tolerations 实现隔离 Taints 和 Tolerations 是 Kubernetes 中用于节点调度的机制。通过给节点添加 taints&#xff08;污点&…...

WPF实战学习笔记18-优化设计TodoView

文章目录 优化设计TodoView修复新增项目无法编辑问题增加了对完成状态的区分增加了选项卡删除功能更新删除请求URI添加删除命令并初始化UI添加删除按钮更改控制器 增加查询结果为空的图片增加转换器修改UI添加资源、命名空间 添加相关元素 增加了根据状态查询的功能Mytodo.Serv…...

Python版day59

503. 下一个更大元素 II 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序&#xff0c;这个数字之后的第一个比它更大的数&…...

[SQL挖掘机] - 算术运算符

在 sql 中&#xff0c;算术运算符主要用于执行数值计算操作&#xff0c;并且在查询语句中具有重要的地位。下面是算术运算符在 sql 中的一些作用和地位&#xff1a; 进行数值计算&#xff1a;算术运算符可以对数值类型的数据进行加减乘除等数值计算操作。例如&#xff0c;可以…...

机器学习基础 数据集、特征工程、特征预处理、特征选择 7.27

机器学习基础 1. 数据集 2. 特征工程 3. 学习分类 4. 模型 5. 损失函数 6. 优化 7. 过拟合 8. 欠拟合数据集 又称资料集、数据集合或者资料集合&#xff0c;是一种由数据所组成的集合特征工程 1. 特征需求 2. 特征设计 3. 特征处理特征预处理、特征选择、特征降维 4. 特征验…...

Sass 常用的功能!

Sass 常用功能 Sass 功能有很多&#xff0c;这边只列举一些比较常用的。 嵌套规则 (Nested Rules) Sass 允许将一套 CSS 样式嵌套进另一套样式中&#xff0c;内层的样式将它外层的选择器作为父选择器。 编译前 .box {.box1 {background-color: red;}.box2 {background-col…...

chmod命令详细使用说明

chmod命令详细使用说明 chmod是Unix和类Unix系统上用于更改文件或目录权限的命令。它是"change mode"的缩写。在Linux和其他类Unix操作系统中&#xff0c;文件和目录具有权限位&#xff0c;用来控制哪些用户可以访问、读取、写入或执行它们。chmod命令允许用户修改这…...

ICC2如何计算Gate Count?

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f;知识星球入口 我们认为gate count等于standard cell(非physical only)总面积 / 最小驱动二输入与非门面积。 ICC2没有专门的命令去报告gate count&#xff0c;只能自己计算&#xff0c;使用report_d…...

Qtday3作业

作业 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QPushButton> #include <QTextToSpeech> #include <QWidget> #include <QDebug> #include <QTimer> //定时器类 #include <QTime> //时间类 #include <QTimerEvent>…...

全球程序员需要知道的50+网址,有多少你第一次听说?

作为程序员&#xff0c;需要知道的50网址&#xff0c;有多少你第一次听说 GitHub (github.com): 最大的代码托管平台&#xff0c;开源项目和代码分享的社区。程序员可以在这里找到各种有趣的项目&#xff0c;参与开源贡献或托管自己的代码。 Stack Overflow (stackoverflow.co…...

Matlab中实现对一幅图上的局部区域进行放大

大家好&#xff0c;我是带我去滑雪&#xff01; 局部放大图可以展示图像中的细节信息&#xff0c;使图像更加直观和精美&#xff0c;此次使用magnify工具实现对绘制的figure选择区域绘制&#xff0c;图像效果如下&#xff1a; 1、基本图像绘制 这里选择绘制一个散点图&#xff…...

mysql-速成补充

目录 1.演示事务 ​编辑 1.1 read-uncommitted 1.2 read-committed 1.3 repeatable read 1.4 幻读 1.5 serializable 1.6 savepoint 2 变量 2.1 语法 2.2 举例 3 存储过程和函数 3.1 特点和语法 3.2 举例 4.函数 4.1 语法 4.2 举例 5 流程控制 5.1 分…...

微信小程序,商城底部工具栏的实现

效果演示&#xff1a; 前提条件&#xff1a; 去阿里云矢量图标&#xff0c;下载8个图标&#xff0c;四个黑&#xff0c;四个红&#xff0c;如图&#xff1a; 新建文件夹icons&#xff0c;把图标放到该文件夹&#xff0c;然后把该文件夹移动到该项目的文件夹里面。如图所示 app…...

Lab———Git使用指北

Lab———Git使用指北 &#x1f916;:使用IDEA Git插件实际工作流程 &#x1f4a1; 本文从实际使用的角度出发&#xff0c;以IDEA Git插件为基本讲述了如果使用IDEA的Git插件来解决实际开发中的协作开发问题。本文从 远程仓库中拉取项目&#xff0c;在本地分支进行开发&#x…...

ChatGPT的工作原理:从输入到输出

&#x1f337;&#x1f341; 博主 libin9iOak带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——libin9iOak的博客&#x1f390; &#x1f433; 《面试题大全》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33…...

redis数据库与主从复制

目录 一 基本操作 二 执行流程 三 reids持久化 四 rdb和aof持久化的过程 五 为什么会有内存碎片 六 redis组从复制 一 基本操作 set :存放数据 例如 set 键值 内容 set k kokoko k就是键值 kokoko就是内容 get:获取数据 例如 get k 就会出来 k对应的数据 keys 查询键…...

js加载和长任务

js加载和长任务 本文将讲解以下浏览器如何加载js&#xff0c;并介绍一些可以提高网页加载速度的方法。 Evaluate Script 如果我们在devtools的performance中分析过网站的加载性能&#xff0c;可能会看到一个很长的任务&#xff0c;叫做Evaluate Script. 在这种情况下&#x…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

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

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...