数据结构——串
串是一种数据元素为字符的特殊的线性表。
1. 串的定义
零个或多个字符(字母、数字或其他字符)组成的有限序列。记为 S="a1a2...an"S="a1a2...an",长度为 nn,空串长度为0。
2.串的术语
- 串长度:串中字符的个数。
- 空串:零个字符的串。即:"",通常用φ表示。
- 字符位置:字符在序列中的序号。
- 空格串:由一个或多个空格组成的串。
- 子串:串中任意个连续的字符组成的子序列。
- 主串:包含子串的串。
- 子串位置:子串的第一个字符在主串中的位置。
- 串相等:两个串的值相等,即两个串的长度相等,各个对应位置的字符都相等。
3.串的基本运算
- strassign (s, chars) //串赋值
- strCompare (S,T) //串比较
- strLength(S) //求串长
- concat(T, S1, S2) //串联接
- subString(S, sub, pos, len) //求子串
- strCopy(T, S) //串拷贝
- strEmpty(S) //串判空
- clearString (S) //清空串
- index(S, T, pos) //子串的位置
- replace(S, T, V) //串替换
- strInsert(S, pos, T) //子串插入
- strDelete(S, pos, len) //子串删除
4. 串的存储结构
-
顺序存储:使用数组存储字符,末尾可加结束符(如C的
\0
)。优点:随机访问高效;缺点:插入/删除需移动元素。 -
链式存储:每个节点存储一个或多个字符,通过指针链接。优点:动态扩展方便;缺点:空间利用率低,操作复杂。
5. 模式匹配算法
(1)暴力匹配(Brute-Force)
-
过程:主串指针
i
和模式串指针j
逐个比较,失败时i
回溯到i-j+1
,j
重置为0。 -
时间复杂度:O(mn)O(mn)。
(2)KMP算法
-
核心思想:利用部分匹配信息(最长公共前后缀),避免主串回溯。
-
步骤:
构造next数组:记录模式串每个位置的最长公共前后缀长度。
匹配过程:主串指针i
不回溯,模式串指针j
根据next
数组跳转。
-
next数组构造:
void getnext( SqString T, int next[ ] ) { int j, k;next[0] = -1; j = 0; k = -1; //k=next[j]while( j < T.length-1 ){ if ( k == -1 || T.str[j] == T.str[k] ) { next[j+1] = k+1;j++;k++; //k=next[j]} else k = next[k]} }
-
时间复杂度:O(m+n)O(m+n),适用于频繁匹配的场景。
6. 代码示例(KMP算法实现)
int Index_KMP( SqString S, SqString T )
{ int i, j, next[200];getnext(T, next);i=0; j=0;while( i<S.length && j<T. length ){ if( j == -1|| S.str[i] ==T.str[j] ){ i++; j++; }else j = next[j];}if(j>=T.length) return i-T.curlen+1; //返回位序 else return 0;
}
总结
串是数据处理的基础结构,其高效操作依赖于合理的存储设计和算法选择。掌握KMP算法及其next数组的构造是解决复杂字符串匹配问题的关键。实际应用中需结合场景权衡不同方法的优缺点。
相关文章:
数据结构——串
串是一种数据元素为字符的特殊的线性表。 1. 串的定义 零个或多个字符(字母、数字或其他字符)组成的有限序列。记为 S"a1a2...an"S"a1a2...an",长度为 nn,空串长度为0。 2.串的术语 串长度…...
使用python爬取网络资源
整体思路 网络资源爬取通常分为以下几个步骤: 发送 HTTP 请求:使用requests库向目标网站发送请求,获取网页的 HTML 内容。解析 HTML 内容:使用BeautifulSoup库解析 HTML 内容,从中提取所需的数据。处理数据ÿ…...
【MySQL | 七、存储引擎是什么?】
存储引擎是什么?作用于哪里? 1. 存储引擎的定义 存储引擎(Storage Engine)是数据库管理系统中负责 数据的存储、检索和管理 的核心组件。它决定了数据如何存储在磁盘上,以及如何从磁盘中读取数据。存储引擎是数据库与…...
Linux -- 进程间通信(IPC)-- 进程间通信、管道、system V 共享内存、system V 消息队列、责任链模式 、system V 信号量
一、什么是进程间通信 1.进程间通信的目的 数据传输:一个进程需要将它的数据发送给另一个进程。资源共享:多个进程之间共享同样的资源。通知事件:一个进程需要向另一个或一组进程发送消息,通知它(它们)发…...
远程登录服务(ssh)
一、远程登录服务概述 1. 概念 远程登录服务就像是一个神奇的桥梁,它让你能够跨越物理距离,通过网络连接到另一台计算机上进行操作。无论你身在何处,只要有网络连接,你就可以像坐在目标计算机前一样进行各种操作。 2. 功能 分享…...
【从零实现Json-Rpc框架】- 项目设计篇
📢博客主页:https://blog.csdn.net/2301_779549673 📢博客仓库:https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! &…...
EtherCAT转CANopen配置CANopen侧的PDO映射
EtherCAT转CANopen配置CANopen侧的PDO映射 在工业自动化领域,EtherCAT和CANopen是两种广泛应用的通信协议。它们各自具有独特的优势,但在某些应用场景下,需要将这两种协议进行转换以实现设备间的高效数据交换。本文将详细介绍如何在使用Ethe…...
Vite管理的Vue3项目中monaco editer的使用以及组件封装
文章目录 背景环境说明安装流程以及组件封装引入依赖封装组件 外部使用实现效果 v-model实现原理 背景 做oj系统的时候,需要使用代码编辑器,决定使用Monaco Editor,但是因为自身能力问题,读不懂官网文档,最终结合ai和网友的帖子成功引入&…...
完整的类在JVM中的生命周期详解
首先给出一个示例代码: 示例的目标是展示一个多功能的类结构,包含继承、接口实现、静态成员、本地方法、线程安全等特性,同时模拟一个简单的“计算器”场景,计算并管理数字。(尽量将所有的 Java 组件和关键字都给出&am…...
大数据学习栈记——HBase操作(shell java)
本文介绍HBase在shell终端的常见操作以及如何利用java api操作HBase,操作系统:Ubuntu24.04 参考: https://blog.51cto.com/u_16099228/8016429 https://blog.csdn.net/m0_37739193/article/details/73618899 https://cloud.tencent.com/d…...
【商城实战(65)】退换货流程全解析:从前端到后端的技术实现
【商城实战】专栏重磅来袭!这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建,运用 uniapp、Element Plus、SpringBoot 搭建商城框架,到用户、商品、订单等核心模块开发,再到性能优化、安全加固、多端适配,乃至运营推广策略,102 章内容层层递进。无论是想…...
改进BM25稀疏检索和BGE稠密检索
改进BM25稀疏检索和BGE稠密检索 检索算法层面 混合检索策略优化 自适应加权融合:在BM25和BGE等混合检索时,根据查询文本的特征(如长度、专业术语占比等)动态调整两者的权重。例如,对于包含大量专业术语的查询,增加BGE的权重;对于关键词明确的简单查询,增加BM25的权重。…...
WPS二次开发系列:以自动播放模式打开PPT文档
在前面文章中 android 调用wps打开文档并感知保存事件 介绍了如何使用WPS SDK打开文档,那么我们是否能够实现在打开WPS 文档的时候能够传递一些参数来控制打开文档的行为呢,经过研究WPS SDK相关文档和API,最终实现了 以自动播放方式打开PPT文…...
当AI重构编程范式:Java 24的进化逻辑与技术深水区的战略突围
一、语言进化的底层密码:从“工具适配”到“定义规则” 在2025年3月19日发布的Java 24中,Oracle以"30周年技术宣言"的姿态展示了编程语言进化的新范式。该版本不仅包含模式匹配、结构化并发等21项JEP特性,更通过后量子加密、AI原生…...
air780eq 阿里云
硬件:APM32F030C8 Air 780eq 参考文档: 合宙780E-4G模块通过AT指令连接到阿里云平台,实现信息的收发_air780e上传阿里云属性值at命令-CSDN博客 阿里云 - atair780eq - 合宙文档中心 4G模块接入阿里云-实现数据上传和命令下发_4g模块上传…...
网络安全之vlan实验
在对vlan进行一定的学习之后我们来练习一个小实验来加深理解记忆 首先是对实验进行一个搭建 第一部分:给交换机配置vlan 首先是sw1 [Huawei]vlan batch 2 to 5 [Huawei]int g0/0/1 [Huawei-GigabitEthernet0/0/1]port hybrid tagged vlan 2 [Huawei-GigabitEthe…...
mac命令行快捷键
光标移动 Ctrl A: 将光标移动到行首。Ctrl E: 将光标移动到行尾。Option 左箭头: 向左移动一个单词。Option 右箭头: 向右移动一个单词。 删除和修改 Ctrl K: 删除从光标到行尾的所有内容。Ctrl U: 删除从光标到行首的所有内容。Ctrl W: 删除光标前的一个单词。Ctrl …...
计算机网络 - OSI 七层模型
OSI 七层模型 OSI(Open System Interconnection,开放系统互联)模型由 ISO(国际标准化组织) 制定,目的是为不同计算机网络系统之间的通信提供一个标准化的框架。它将网络通信划分为 七个层次,每…...
TCP/IP 协议族详细知识点清单
📚 TCP/IP 协议族详细知识点清单 一、概述与体系结构 🌐 TCP/IP 协议模型(四层模型) 层次协议功能应用层HTTP、FTP、DNS、SMTP提供应用服务传输层TCP、UDP端到端传输,可靠或不可靠网络层IP、ICMP、ARP、RARP寻址、路…...
Vue3(自定义指令directive详解)
文章目录 前言一、自定义指令的生命周期钩子二、自定义指令的创建与注册使用三、扩展 简化形式总结 前言 在Vue3中,自定义指令是一种强大的工具,允许开发者扩展和增强HTML元素的功能。以下是对Vue3中自定义指令的详细解析: 一、自定义指令…...
Redis--redis客户端
目录 一、引言 二、数据库管理命令 三、redis客户端 四、Java客户端使用Redis 五、相关命令使用 1.get,set 2.exists,del 3.keys 4.expire,ttl 六、总结 一、引言 在之前学了redis相关类型命令之后,本篇文章,…...
【高项】信息系统项目管理师(十)项目风险管理【5分】
项目风险是一种不确定的事件或条件,一旦发生,会对项目目标产生某种正面或负面的影响。项目风险既包括对项目目标的威胁,也包括促进项目目标的机会。已知风险是那些已经经过识别和分析的风险,对于已知风险,对其进行规划,寻找应对方案是可行的;虽然项目经理们可以依据以往…...
jenkins批量复制视图项目到新的视图
1、当前视图为 测试2分支,创建了新的视图为国际化预生产 2、进入系统设置的脚本管理 import hudson.model.* //源view def str_view "测试2分支" //目标view def str_new_view "国际化预生产" //源job名称(模糊匹配) def str_search &qu…...
uv:Rust 驱动的 Python 包管理新时代
在 Python 包管理工具层出不穷的今天,pip、pip-tools、poetry、conda 等各有千秋。而今天要介绍的 uv,则是一款由 Astral 团队推出、采用 Rust 编写的全新工具,目标直指成为 “Python 的 Cargo”。它不仅在性能上表现优异,而且在功…...
GD32 ISP下载程序(串口烧录)
一、下载烧录软件 下载地址兆易创新GigaDevice-资料下载兆易创新GD32 MCUhttps://www.gd32mcu.com/cn/download?kwGD32All-In-OneProgrammer&lancn 二、使用USB转串口连接GD32开发板 这里使用GD32E230C8T6为例: GD32E230C8T6USB 转串口模块说明PA9ÿ…...
Spring MVC 配置详解与入门案例
目录 引言 一、Spring MVC 的发展背景 1. Model I 与 Model II 2. MVC 模式 二、Spring MVC 入门案例 1. 创建 WEB 工程并引入依赖 2. 配置 web.xml 3. 配置 springmvc.xml 4. 创建控制器和视图 5. 部署并测试 三、Spring MVC 原理 1. 核心组件 2. 请求处理流程 …...
【10万QPS压力测试】Redis三主三从高可用集群基准测试
📕我是廖志伟,一名Java开发工程师、《Java项目实战——深入理解大型互联网企业通用技术》(基础篇)、(进阶篇)、(架构篇)清华大学出版社签约作家、Java领域优质创作者、CSDN博客专家、…...
git的进阶使用
一.协作冲突 举个简单的例子,公司里两个人(A,B)同一天上班,都拉取了远程仓库数据。然后A做完了所有的工作,进行了x文件的修改并提交至远程仓库。而B在做自己工作的时候不小心或者需要修改x文件,B认为A没有操作x文件直接push没有问…...
23种设计模式-责任链(Chain of Responsibility)设计模式
责任链设计模式 🚩什么是责任链设计模式?🚩责任链设计模式的特点🚩责任链设计模式的结构🚩责任链设计模式的优缺点🚩责任链设计模式的Java实现🚩代码总结🚩总结 🚩什么是…...
MySQL复习
1基本操作复习 1.1数据库创建 创建数据库create database 数据库名;判断再创建数据库create database if not exists 数据库名;创建数据库指定字符集create database 数据库名 character set 字符集;创建数据库指定排序方式create database 数据库名 collate 排序方式;创建数据…...
【嵌入式学习2】c语言重点整理
目录 ## 重点掌握 1、数组 2、指针 3、结构体 4、函数 回调函数的常见用途 ## 如何区分数组指针,指针数组,函数指针,结构体指针,指针偏移量 ## 重点掌握 1、数组 https://blog.csdn.net/weixin_60546365/article/details…...
java项目之基于ssm的个人博客网站(源码+文档)
项目简介 个人博客网站实现了以下功能: 个人博客网站在Eclipse环境中,使用Java语言进行编码,使用Mysql创建数据表保存本系统产生的数据。系统可以提供信息显示和相应服务,其管理员审核博客文章和相册分享信息,管理文…...
C++学习之路:从头搞懂配置VScode开发环境的逻辑与步骤
目录 编辑器与IDE基于vscode的C开发环境配置1. 下载vscode、浅尝编译。番外篇 2. 安装插件,赋能编程。3. 各种json文件的作用。c_cpp_properties.jsontask.jsonlaunch.json 总结&&彩蛋 编辑器与IDE 上一篇博客已经介绍过了C程序的一个编译流程,从…...
deploy myEclipse j2ee project to server没反应
解决办法 1.如果工作空间的问题,那么需要删除你工作空间的一个文件就可以解决了。 这个文件在Myeclipse工作区(workspace) .metadata\.plugins\org.eclipse.core.runtime\.settings目录...
react项目中当组件渲染的时候如何执行接口
最近遇到一个场景,就是组件渲染的时候去调用接口进行数据回填。这个在vue中很简单,在created生命周期函数中,直接调用接口即可。但是react没有created生命周期,所以在react中我们需要用到useEffect钩子函数。 在 React 函数组件中…...
python虚拟环境安装opus(windows)
python -m venv venv 创建虚拟环境后,并且安装软件包后,运行项目报错,提示如下: Could not find Opus library. Make sure it is installed 原因是缺少opus.dll, (先把项目内所有使用的第三方库都安装完成) 从以下页面下载.dll文件之后,放入venv\Scripts目录下即可 https://…...
手机怎么换网络IP有什么用?操作指南与场景应用
在数字化时代,手机已经成为我们日常生活中不可或缺的一部分,无论是工作、学习还是娱乐,手机都扮演着至关重要的角色。而在手机的使用过程中,网络IP地址作为设备在互联网上的唯一标识符,其重要性和作用不容忽视。本文将…...
小程序内表格合并功能实现—行合并
功能介绍:支付宝小程序手写表格实现行内合并,依据动态数据自动计算每次需求合并的值,本次记录行内合并,如果列内合并,同理即可实现 前端技术:grid布局 display:grid 先看实现效果: axml&…...
基于Flask的通用登录注册模块,并代理跳转到目标网址
实现了用户密码的加密,代理跳转到目标网址,不会暴露目标路径,未登录的情况下访问proxy则自动跳转到登录页,使用时需要修改配置项config,登录注册页面背景快速修改,可以实现登录注册模块的快速复用。 1.app…...
nlohmann::json教程
nlohmann::json 核心函数和方法 1. 基础构造与初始化 函数/方法描述示例json j;创建一个空的 JSON 对象(默认是 object 类型)json j;json::object()显式创建一个空的 JSON 对象json j json::object();json::array()显式创建一个空的 JSON 数组json ar…...
多层感知机从0开始实现
《动手学深度学习》-4.2-笔记 多层感知机在输出层和输入层之间增加一个或多个全连接隐藏层,并通过激活函数转换隐藏层的输出。 常用的激活函数包括ReLU函数、sigmoid函数和tanh函数。 import torch from torch import nn from d2l import torch as d2lbatch_size …...
在K8S中使用ArgoCD做持续部署
一、了解argocd ArgoCD是一个基于Kubernetes的GitOps持续交付工具,应用的部署和更新都可以在Git仓库上同步实现,并自带一个可视化界面。本文介绍如何使用GitArgocd方式来实现在k8s中部署和更新应用服务。关于ci这一块这里不多介绍。主要讲解argocd如何实…...
Python中数据结构元组详解
在Python中,元组(Tuple)是一种不可变的序列类型,常用于存储一组有序的数据。与列表(List)不同,元组一旦创建,其内容无法修改。本文将详细介绍元组的基本操作、常见运算、内置函数以及…...
23种设计模式-命令(Command)设计模式
命令设计模式 🚩什么是命令设计模式?🚩命令设计模式的特点🚩命令设计模式的结构🚩命令设计模式的优缺点🚩命令设计模式的Java实现🚩代码总结🚩总结 🚩什么是命令设计模式…...
计算机网络——数据链路层的功能
目录 物理链路 逻辑链路 封装成帧(组帧) 帧定界 透明传输 SDU 差错控制 可靠传输 流量控制 介质访问控制 主机需要实现第一层到第五层的功能,而路由器这种节点只需要实现第一层到第三层的这些功能 假设左边用户需要给右边用户发送…...
Axure项目实战:智慧城市APP(一)首页(动态面板、拖动效果)
亲爱的小伙伴,在您浏览之前,烦请关注一下,在此深表感谢! 课程主题:智慧城市APP 主要内容:首页、政务公告、公交查询页面设计 应用场景:各类政务型、B端APP均可参考 案例展示:&am…...
Unity网络开发快速回顾
知识点来源:总结人间自有韬哥在, 唐老狮,豆包 目录 1.网络通信-通信必备知识-IP地址和端口类2.网络通信中序列化和反序列化2进制数据3.Socket类4.TCP同步服务端和客户端基础实现4.1.服务端基本实现4.2.客户端实现: 5.区分消息类型…...
鸿蒙学习笔记(1)-文件解读、编写程序、生命周期
一、文件解读 .hvigor:装有一些编译过程中的依赖缓存。 .idea:工具自动生成的,标记我们的工具是基于idea。 AppScope:代表着整个APP的配置,最后打包使用。之中的resources目录下是应用的名称和图片存放路径,其中app.json5: bund…...
多维动态规划 力扣hot100热门面试算法题 面试基础 核心思路 背题
多维动态规划 不同路径 https://leetcode.cn/problems/unique-paths/ 核心思路 比较简单 f[i][j] f[i - 1][j] f[i][j - 1] ; 示例代码 class Solution {public int uniquePaths(int n, int m) {int[][] f new int[n][m];for (int i 0; i < n; i)f[i][0] 1;for…...
C++ 多线程简要讲解
std::thread是 C11 标准库中用于多线程编程的核心类,提供线程的创建、管理和同步功能。下面我们一一讲解。 一.构造函数 官网的构造函数如下: 1.默认构造函数和线程创建 thread() noexcept; 作用:创建一个 std::thread 对象,但…...