数据结构之串
一、串的定义与基本概念
1. 串的定义
定义:串是由零个或多个字符组成的有限序列,记作 s="a1a2…an",例如 "data structure"、"123" 等。
- 空串:无任何字符,长度为 0,用
""
表示,例如短信内容为空时即为空串。 - 空格串:由一个或多个空格组成,有长度,例如 " "(3 个空格)。
- 子串与主串:子串是主串中连续字符序列。
- 生活实例:回文诗 “上海自来水来自海上” 是一个串,其正读和反读相同,体现了串的逆序特性;英文单词 “friend” 中,“end” 是子串,“friend” 是主串。
2. 串的比较
规则:基于字符的 ASCII/Unicode 编码逐个比较,直到找到首个不同字符或遍历完较短串。
- 例 1:"apple" vs "apricot",前两个字符 “ap” 相同,第三个字符 “p”(ASCII 112)<“r”(ASCII 114),故 "apple" < "apricot"。
- 例 2:"abc" vs "ab",前两个字符相同,短串先遍历完,故 "abc" > "ab"。
二、串的抽象数据类型(ADT)
基本操作
-
赋值:将一个串的内容复制到另一个串。
-
比较:逐个字符按ASCII码值比较,决定串的大小关系。
-
连接:将两个串首尾相连,形成新串。
-
求子串:从主串的指定位置截取固定长度的子串。
-
替换:将主串中某子串替换为另一个串。
-
插入:在指定位置插入子串。
-
删除:删除主串中指定位置的子串。
生活实例:微信聊天时,发送前编辑文字(赋值)、转发消息(复制)、撤回消息(清空),以及搜索聊天记录中的关键词(定位),都是串操作的典型应用。
三、串的存储结构
1. 顺序存储
- 用数组存储,如 C 语言中用
char str[100]
存储字符串。 - 优缺点:
- 优点:随机访问快(如取第 5 个字符直接通过下标)。
- 缺点:插入 / 删除需移动元素,可能溢出。
- 生活实例:手机短信长度限制(如 70 字),若输入超过,需截断或分段,类似顺序存储的固定容量限制。
2. 链式存储
- 用链表结点存储字符,每个结点可存多个字符以减少空间浪费。
- 优点:动态灵活,插入 / 删除方便(如聊天记录不断新增,无需预先分配固定长度)。
- 缺点:随机访问慢,需遍历。
四、模式匹配算法
1. 朴素模式匹配算法
- 思路:从主串每个位置开始,逐个字符匹配子串,最坏时间复杂度 O((n−m+1)×m)。
- 生活实例:在一本小说中查找 “英雄” 一词,每次从当前位置开始逐字对比,若每次都在子串末尾发现不匹配(如主串是 “英雄气短”,子串是 “英雄豪杰”),需多次回溯,效率低。
2. KMP 算法
-
核心思想:利用部分匹配信息避免不必要的回溯。
-
部分匹配表(Next数组):
-
定义:
next[j]
表示模式串前 𝑗j 个字符的最长公共前后缀长度。 -
计算示例(模式串
"ABCDABD"
):j 0 1 2 3 4 5 6 模式串 A B C D A B D next[j] -1 0 0 0 0 1 2 -
匹配过程:当字符失配时,模式串右移 𝑗−𝑛𝑒𝑥𝑡[𝑗]j−next[j] 位。
-
-
时间复杂度:𝑂(𝑛+𝑚)O(n+m),显著优于朴素算法。
六、KMP算法的实现细节
-
Next数组的推导:
-
初始化
next[0] = -1
。 -
通过递推计算每个位置的
next[j]
,利用已计算的next
值减少重复比较。
-
-
优化Next数组:
-
若
pattern[j] == pattern[next[j]]
,则nextval[j] = nextval[next[j]]
,进一步减少比较次数。 -
代码示例:
-
#include <iostream>
#include <string>
#include <vector>// 朴素模式匹配算法
int naivePatternMatching(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();for (int i = 0; i <= n - m; ++i) {int j;for (j = 0; j < m; ++j) {if (text[i + j] != pattern[j]) {break;}}if (j == m) {return i;}}return -1;
}// 计算next数组
void computeNext(const std::string& pattern, std::vector<int>& next) {int m = pattern.length();int len = 0;next[0] = 0;int i = 1;while (i < m) {if (pattern[i] == pattern[len]) {len++;next[i] = len;i++;}else {if (len != 0) {len = next[len - 1];}else {next[i] = 0;i++;}}}
}// KMP算法
int kmpPatternMatching(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();std::vector<int> next(m);computeNext(pattern, next);int i = 0;int j = 0;while (i < n) {if (pattern[j] == text[i]) {j++;i++;}if (j == m) {return i - j;}else if (i < n && pattern[j] != text[i]) {if (j != 0) {j = next[j - 1];}else {i = i + 1;}}}return -1;
}int main() {std::string text = "ABABDABACDABABCABAB";std::string pattern = "ABABCABAB";// 朴素模式匹配int naiveIndex = naivePatternMatching(text, pattern);if (naiveIndex != -1) {std::cout << "朴素模式匹配: 模式串在主串中的位置是 " << naiveIndex << std::endl;}else {std::cout << "朴素模式匹配: 未找到模式串" << std::endl;}// KMP模式匹配int kmpIndex = kmpPatternMatching(text, pattern);if (kmpIndex != -1) {std::cout << "KMP模式匹配: 模式串在主串中的位置是 " << kmpIndex << std::endl;}else {std::cout << "KMP模式匹配: 未找到模式串" << std::endl;}return 0;
}
相关文章:
数据结构之串
一、串的定义与基本概念 1. 串的定义 定义:串是由零个或多个字符组成的有限序列,记作 s"a1a2…an",例如 "data structure"、"123" 等。 空串:无任何字符,长度为 0,…...
基于腾讯云MCP广场的AI自动化实践:爬取小红书热门话题
基于腾讯云MCP广场的AI自动化实践:爬取小红书热门话题 我正在参加Trae「超级体验官」创意实践征文,本文所使用的 Trae 免费下载链接:www.trae.com.cn/?utm_source… 🔎 背景 在人工智能快速发展的时代,AI技术不仅重…...
AI领域的MCP(Model-Centric Paradigm)
1. 什么是MCP(Model-Centric Paradigm)? MCP(Model-Centric Paradigm)是人工智能开发中的一种核心理念,强调以模型的优化与改进作为主要驱动因素来提升AI系统的表现。在MCP模式下,开发者专注于…...
裸辞8年前端的面试笔记——JavaScript篇(一)
裸辞后的第二个月开始准备找工作,今天是第三天目前还没有面试,现在的行情是一言难尽,都在疯狂的压价。 下边是今天复习的个人笔记 一、事件循环 JavaScript 的事件循环(Event Loop)是其实现异步编程的关键机制。 从…...
力扣刷题Day 41:除自身以外数组的乘积(238)
1.题目描述 2.思路 方法1:搞一个数组存放各元素之前所有数的乘积(头为1),再搞一个数组存放各元素之后所有数的乘积(尾为1)。 方法2:上面的方法是很好理解的,在此基础上应该如何优化…...
金仓数据库征文-金仓KES数据同步优化实践:逻辑解码与增量同步
目录 一.同步场景与方案选型 二.同步环境配置 1.前置条件验证 2.逻辑解码配置 三.同步实施与问题排查 1.结构映射规则 2.增量数据捕获 3.数据一致性校验 四.性能调优实践 1.同步线程优化 2.批量提交优化 3.资源监控指标 五.典型场景解决方案 1.双向同步冲突处理 …...
【前端基础】9、CSS的动态伪类(hover、visited、hover、active、focus)【注:本文只有几个粗略说明】
一、什么是伪类 选择器的一种,用于选择处于特定状态的元素。 最常见的现象:鼠标放在某些文字上面,文字就会加上颜色。 鼠标没放上去之前: 鼠标放上去之后: 二、动态伪类 图片来源(链接文章也有其他伪…...
企业开发平台大变革:AI 代理 + 平台工程重构数字化转型路径
在企业数字化转型的浪潮中,开发平台正经历着前所未有的技术革命。从 AST(抽象语法树)到 AI 驱动的智能开发,从微服务架构到信创适配,这场变革不仅重塑了软件开发的底层逻辑,更催生了全新的生产力范式。本文…...
ZooKeeper工作机制与应用场景
目录 1.1、概述1.2、选举机制1.2.1、选举触发条件1.2.2、选举规则1.2.3、选举过程详解 1.3、数据同步机制1.3.1、正常同步1.3.2、宕机同步 1.4、客户端常用命令1.5、应用场景1.5.1、配置管理1.5.2、命令服务1.5.3、分布式锁服务1.5.4、集群管理1.5.5、分布式ID1.5.6、分布式协调…...
VR制作软件用途(VR制作软件概述)
虚拟现实(VR)制作软件作为现代科技的瑰宝,正以独特的魅力重塑各行各业。 通过构建三维虚拟环境,这些软件提供了前所未有的沉浸式体验,还推动了技术革新与产业升级。本文将探讨VR制作软件的主要用途,并重点…...
【PostgreSQL数据分析实战:从数据清洗到可视化全流程】电商数据分析案例-9.1 业务场景与数据准备
👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路 文章大纲 9.1 业务场景与数据准备9.1.1 业务场景描述核心业务目标业务挑战 9.1.2 数据来源与获取数据源构成数据获取方案 9.1.3 数据结构与字段说明核心数据表设计1. 订单事实表&…...
PyTorch 入门与核心概念详解:从基础到实战问题解决
PyTorch 入门与核心概念详解:从基础到实战问题解决 前言 用PyTorch 编写 Transformer 模型时遇到了多个错误,包括维度不匹配、NaN 损失、注意力权重未记录以及 OpenMP 库初始化等问题。 本文基于以上,对 PyTorch 的基本解释,并对…...
【办公类-99-05】20250508 D刊物JPG合并PDF便于打印
背景需求 委员让我打印2024年2025年4月的D刊杂志,A4彩打,单面。 有很多JPG,一个个JPG图片打开,实在太麻烦了。 我需要把多个jpg图片合并成成为一个PDF,按顺序排列打印。 deepseek写Python代码 代码展示 D刊jpg图片合…...
【C++】手搓一个STL风格的string容器
C string类的解析式高效实现 GitHub地址 有梦想的电信狗 1. 引言:字符串处理的复杂性 在C标准库中,string类作为最常用的容器之一,其内部实现复杂度远超表面认知。本文将通过一个简易仿照STL的string类的完整实现,揭示其设…...
无实体对话式社交机器人 拟人化印象形成机制:基于多模态交互与文化适配的拓展研究
《如何感知AI对话者:无实体对话式社交机器人拟人化对其印象形成效果影响机制的实验研究》解析 一、研究背景与核心问题 (一)技术背景与研究动机 随着生成式AI技术发展,以ChatGPT、文心一言为代表的无实体对话式社交机器人兴起,用户对其高度拟人化特征有显著需求,如扮演…...
存储器:DDR和独立显卡的GDDR有什么区别?
本文来简要对比DDR(Double Data Rate SDRAM)和GDDR(Graphics Double Data Rate SDRAM)的区别,重点说明它们在设计、性能和应用上的差异: 1. 设计目标与架构 DDR:通用型DRAM,设计为…...
viewDesign里的table内嵌套select动态添加表格行绑定内容丢失
问题 描述 viewDesign里的table内嵌套select,表格的行数是手动点击按钮添加的,添加第一行选择select的内容能正常展示,添加第二行第一行的select的内容消失 代码 <FormItem label"内饰颜色"><Tableclass"mt_10&q…...
vue v-html无法解析<
vue v-html无法解析字符串的小于号 方法一:可以替换成转义符 (实际还是会报错) let str 12345<445667 str.replaceAll(<, <)方法二:可以替换成中文小于号 let str 12345<445667 str.replaceAll(<, <)...
COLT_CMDB_linux_userInfo_20250508.sh修复历史脚本输出指标信息中userName与输出信息不一致问题
#!/bin/bash #IT_BEGIN #IT_TYPE3 #IT SYSTEM_LINUX_AGENTUSERDISCOVER|discovery.user[disc] #原型指标 #IT_RULE SYSTEM_LINUX_AGENTUSERGROUPID|groupId[{#USERNAME}] #IT_RULE SYSTEM_LINUX_AGENTUSERHOME|userHome[{#USERNAME}] #IT_RULE SYSTEM_LINUX_AGENTUSERNAME|user…...
A. Row GCD(gcd的基本性质)
Problem - 1458A - Codeforces 思路: 首先得知道gcd的两个基本性质: (1) gcd(a,b)gcd(a,|b-a|) (2) gcd(a,b,c)gcd(a,gcd(b,c)) 结合题目所给的a1bj,a2bj...... anbj 根据第一条性质得到: gcd(a1bj,a2bj)gcd(…...
k8s术语之Horizontal Pod Autoscaling
应用的资源使用率通常都有高峰和低谷的时候,如何削峰填谷,提高整体的整体资源利用率,让service中的Pod个数自动调整呢?Horizontal Pod Autoscaling:使pod水平自动缩放。这个Object也是最能体现kubernetes之于传统运维价值的地方&a…...
函数级重构:如何写出高可读性的方法?
1. 引言:为什么方法级别的重构如此重要? 在软件开发中,方法(函数)是程序逻辑的基本单元。一个高质量的方法不仅决定了程序是否能正常运行,更直接影响到: 代码的可读性:能否让其他开发者快速理解可维护性:未来修改是否容易出错可测试性:是否便于编写单元测试协作效率…...
手撕基于AMQP协议的简易消息队列-8(单元测试的编写)
在MQTest中编写模块的单元测试 在MQTest中编写makefile文件来编译客户端模块 all:Test_FileHelper Test_Exchange Test_Queue Test_Binding Test_Message Test_VirtualHost Test_Route Test_Consumer Test_Channel Test_Connection Test_VirtualHost:Test_VirtualHost.cpp ..…...
硬件选型:工控机的选择要素
在机器视觉应用中,工控机作为核心计算设备,承担着图像处理、数据分析和设备控制等多重任务。由于机器视觉常常在工业自动化、质量检测和精密控制中发挥重要作用,工控机的选型直接影响系统的性能和可靠性。 1. 应用场景与需求 机器视觉系统广…...
【芯片设计- RTL 数字逻辑设计入门 4.1 -- verilog 组合逻辑和时序逻辑延时比较】
文章目录 Overview时间线简单示意Overview 我们来详细分析下面这段 RTL Code , sbcs_sbbusy 为什么会比 sbcs_sbbusy_nx 慢一拍(晚一个时钟周期变化)。 assign sbcs_sbbusy_nx = set_sbcs_sbbusy;always @(posedge clk or negedge dmi_resetn) beginif (!dmi_resetn) begi…...
关于ubuntu下交叉编译arrch64下的gtsam报错问题,boost中boost_regex.so中连接libicui18n.so.55报错的问题
交叉编译gtsam时遇到的报错信息如下:gtsam需要连接boost, 解决办法: 1.重新编译boost可解决。 2.自己搞定生成一个libicui18n.so.55。 由于我们的boost是公用的,因此1不太可能(我试过重新编译完boost,在编译gtsam完…...
IoT平台和AIoT平台的区别
1. 什么是AIoT平台? AIoT(人工智能物联网,Artificial Intelligence of Things)平台 是 人工智能(AI) 与 物联网(IoT) 深度融合的技术框架,通过将AI算法嵌入物联网终端或…...
iOS 模块化开发流程
iOS模块化开发是一种将大型项目拆分为独立、可复用模块的开发模式,能够提升代码可维护性、团队协作效率和动态交付能力。以下是iOS模块化开发的核心流程与关键要点: 一、模块化设计阶段 业务解耦与模块划分 横向分层:基础层(网络、…...
云原生安全治理体系建设全解:挑战、框架与落地路径
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言:云原生环境下,安全治理正在被重构 在传统IT架构中,安全防护多依赖边界设备(如防火墙、WAF、堡垒机)进行集中式防护。然而,在云原生环境下,这种“边界式”安全模型正面临颠覆。 应用微服务化…...
如何在Vue-Cli中使用Element-UI和Echarts和swiper插件(低版本)
1st.Element-UI 1.1 安装 在终端输入 npm install element-ui 1.2 导入 在全局main.js中全局导入Element-UI: // 导入element-ui组件库 import ElementUI from element-ui; // 导入element-ui组件库的样式 import element-ui/lib/theme-chalk/index.css; // 注…...
[特殊字符]【实战教程】用大模型LLM查询Neo4j图数据库(附完整代码)
🌟 核心要点速览 ✅ 基于LangChain框架实现LLM查询Neo4j ✅ 使用Qwen2.5模型(实测Llama3.1查不出内容) ✅ 包含完整数据准备代码实现效果演示 ✅ GitHub/Gitee源码已同步(文末获取) 🛠️ 环境准备 1️⃣ 安装Neo4j图数据库 # Windows安装指南参考&…...
Qt获取CPU使用率及内存占用大小
Qt 获取 CPU 使用率及内存占用大小 文章目录 Qt 获取 CPU 使用率及内存占用大小一、简介二、关键函数2.1 获取当前运行程序pid2.2 通过pid获取运行时间2.3 通过pid获取内存大小 三、具体实现五、写在最后 一、简介 近期在使用软件的过程中发现一个有意思的东西。如下所示&a…...
算法解密:除自身以外数组的乘积问题详解
算法解密:除自身以外数组的乘积问题详解 一、引言 在算法的奇妙旅程中,我们时常会遇到一些看似简单却蕴含深刻智慧的问题,“除自身以外数组的乘积”就是其中之一。这个问题不仅考验我们对数组操作的熟练程度,还要求我们在特定的限制条件下(不能使用除法且时间复杂度为O(n…...
基于Kubernetes的Apache Pulsar云原生架构解析与集群部署指南(上)
#作者:闫乾苓 文章目录 概念和架构概述主要特点消息传递核心概念Pulsar 的消息模型Pulsar 的消息存储与分发Pulsar 的高级特性架构BrokerBookKeeperZooKeeper 概念和架构 概述 Pulsar 是一个多租户、高性能的服务器到服务器消息传递解决方案。Pulsar 最初由雅虎开…...
信创生态核心技术栈:数据库与中间件
🧑 博主简介:CSDN博客专家、CSDN平台优质创作者,高级开发工程师,数学专业,10年以上C/C, C#, Java等多种编程语言开发经验,拥有高级工程师证书;擅长C/C、C#等开发语言,熟悉Java常用开…...
CMU-15445(3)——PROJECT#1-BufferPoolManager-Task#1
PROJECT#1-BufferPoolManager 在完成了前面基础的PROJECT#0后,从本节开始才正式进入了CMU-15445的学习,最终目的是构建一个面向磁盘的数据库管理系统。 PROJECT#1 的主要任务是实现数据库管理系统的缓冲池管理器,缓冲池负责在主存缓冲区与持…...
《数据结构初阶》【链式二叉树】
《数据结构初阶》【链式二叉树】 前言:---------------树---------------什么是树?📌爱心❤小贴士:树与非树?树的基本术语有哪些?关于节点的一些定义:关于树的一些定义:关于森林的定…...
Oracle免费认证来袭
1、Oracle Cloud Infrastructure 2025 Foundations Associate” 🔗 考证地址:https://mylearn.oracle.com/ou/exam-unproctored/oracle-cloud-infrastructure-2025-foundations-associate-1z0-1085-25/148056/241954 2、Oracle Cloud Infrastructure 2…...
Vim 编辑器常用快捷键速查表
Vim 编辑器常用快捷键速查表 Vim 快捷键大全 **1. 基础操作****2. 光标移动****3. 编辑文本****4. 查找替换****5. 分屏操作****6. 可视化模式** **附:Vim 模式切换流程图** 1. 基础操作 快捷键功能说明i进入插入模式(光标前)a进入插入模式&…...
从父类到子类:C++ 继承的奇妙旅程(1)
前言: 在前文,小编讲述了C模板的进阶内容,下面我们就要结束C初阶的旅行,开始进入C进阶容的旅c程,今天旅程的第一站就是C三大特性之一——继承的旅程,各位扶好扶手,开始我们今天的C继承的奇妙旅程…...
HTML9:页面结构分析
页面结构分析 元素名描述header标题头部区域的内容(用于页面或页面中的一块区域)footer标记脚部区域的内容(用于整个页面或页面的一块区域)sectionWeb页面的一块独立区域article独立的文章内容aside相关的内容或应用(…...
LabVIEW超声波液位计检定
在工业生产、运输和存储等环节,液位计的应用十分广泛,其中超声波液位计作为非接触式液位测量设备备受青睐。然而,传统立式水槽式液位计检定装置存在受建筑高度影响、量程范围受限、流程耗时长等问题,无法满足大量程超声波液位计的…...
maven 安装 本地 jar
命令: mvn install:install-file -DgroupIdnet.pingfang.application -DartifactIdjna -Dversion5.1.0 -Dpackagingjar -DfileD:\maven\repository1\jna\5.1.0\jna-5.1.0.jarmvn:这是Maven的执行命令。 install:install-file:这是Maven插件目…...
leetcode 141. Linked List Cycle
题目描述: 代码: 用哈希表也可以解决,但真正考察的是用快慢指针法。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Soluti…...
【Python】通过`Editable Install`模式详解,解决Python开发总是import出错的问题
摘要 田辛老师在很久以前,写过一篇关于Python的模块、包之间的内部关系的博客,叫做【Python】__init__.py 文件详解。 虽然我觉得这篇文章已经足够了, 但是还是有很多朋友碰到开发的过程中import包报错的问题。 今天, 田辛老师想…...
C 语言网络编程问题:E1696 无法打开 源 文件 “sys/socket.h“
#include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h>在 C 语言网络编程中,上述代码报如下错误 E1696 无法打开 源 文件 "sys/socket.h"E1696 无法打开 源 文件 "netinet/in.h" E1696 无法打开 源 文件…...
操作指南*
任务1: 环境搭建 1.1 创建Spring Boot项目 操作步骤: 使用IDEA创建项目: 打开IDEA → File → New → Project选择 Spring Initializr → 设置项目信息(Group、Artifact、Java版本)选择依赖:Spring Web、MySQL Drive…...
VRM Add-on for Blender 学习笔记
VRM Add-on for Blender 使用教程-CSDN博客 VRM Add-on for Blender 是 Blender 的一个官方插件,主要用于 导入和导出 VRM 格式的 3D 模型。VRM(Virtual Reality Model)是一种开放标准的 3D 人形角色模型格式,起源于日本…...
C++ 完美转发
C 完美转发逐步详解 1. 问题背景与核心目标 在 C 模板编程中,若直接将参数传递给其他函数,参数的 值类别(左值/右值)和 类型信息(如 const)可能会丢失。例如: template<typename T> voi…...
学习记录:DAY23
项目开发与学习记录:字段注入优化 前言 我总有一种什么大的要来了的危机感。还是尽快把项目做起来吧,现在全在弄底层的框架。这是一个两天的blog,前一天bug没修好,气到连blog都没写。 日程 5月7日 晚上7点:本来想玩…...