数据结构基础-串（数据结构串的基本运算）
ztj100 2025-07-15 02:15 1 浏览 0 评论
串
串是仅由字符构成的有限序列，是一种特殊的线性表，其数据元素为字符，因此通常称呼为字符串。一般标记为S='a1a2a3...an'。
- 基本概念
空串：长度为零，不包含任何字符的串。
空格串：由一个或多个空格组成的串（空格也是字符）；
子串：串中任意连续字符构成的序列称为子串，含有子串的串称为主串。子串在主串中的位置是指该子串首次出现时，子串第一个字符在主串中的位置。
串相等：两个串的长度相等，并且对于序列的的字符也相同。
串比较：以字符的ASCII码值做为依据。从两个串的第一个字符开始，字符的码大者，所在的串为大。若其中一个串先结束，则以串长者为大。
如下图JAVA JDK中字符串比较方法所示：
字符串value与字符串anotherString比较，若执行结果为正数，则value大于anotherString，结果为负数，则anotherString大于value。为零，则两个字符串相等。
- 存储结构
顺序存储：
用一组地址连续的存储单元来存储串值得字符序列。可以根据串的字符数定义存储空间，也可以根据串长的需要，动态申请空间。
链式存储：
链的每个结点可以存储一个字符，也可以存储多个字符。因链结点的大小会影响处理效率，所以要考虑存储密度。
- 匹配模式
子串的定位操作，称为串的匹配模式。子串也称为模式串。
朴素的模式匹配算法：
该算法也被称为布鲁特-福斯算法。
该算法的思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对模式串进行后续比较，否则，从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续字符序列相等时为止。如果在主串中找不到与模式串相同的，则匹配失败。
若主串和模式串的长度分别是n和m,则最好情况，时间复杂度为O(n+m)，最坏情况，时间复杂度为O(n*m)。
改进的模式匹配算法（KMP）：
改进之处在于，当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”的字符，将模式串向右滑动尽可能远的距离，再进行比较。具体向右滑动多少距离，就得依据next函数值进行计算。依据模式串next函数值整理的表，就叫《部分匹配表》。
滑动距离=已“部分匹配”的字符数-next函数值。
next函数定义如下：
JAVA脚本如下：
private int[] next(String pattern) {
char[] p = pattern.toCharArray(); //模式串字符组
int[] next = new int[p.length];
next[0] = -1; //定义下标0为字符串的开始，规定next[0]=-1;
int i = 0;
int j = -1;
while(i < p.length - 1) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
相关推荐
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
-
IT之家讯微软已向Insider用户推送了Win10预览版10532更新，本次更新对右键菜单、《Windows反馈》应用以及Edge浏览器进行了改进。除此之外还包含一些Bug，汇总如下，有意升级Wi...
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
-
IT之家讯本月中旬微软向Insider用户推送了Win10Mobile预览版10512，该版本修复了一些Bug，增强了系统稳定性，但依然存在一些问题。今天，微软Insider项目负责人GabeAu...
- 微软开始推送Win10预览版10532快速版更新
-
8月28日消息，刚才，微软推送了Win10Build10532快速版，修复了之前的Bug，并带来了三项改进。主要来说，这次的更新改进了右键菜单的UI，使其更具Modern风格（见上图）。此外，更新...
- Win10预览版10532更新内容大全（windows10更新预览版）
-
IT之家讯今天凌晨微软向Insider用户推送了Win10预览版10532快速版更新，本次更新主要带来了三处改进，汇总如下：o改进右键菜单，外观更加Modern。这是基于网友要求界面一致的反馈做出...
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
-
根据IT之家网友的反映，安装了微软虚拟机Hyper-V的Win10预览版用户无法成功升级Build10532版本，安装过程中会被要求回滚系统。很多朋友在尝试关闭虚拟机之后重启安装程序，结果仍然无法顺...
- Win10预览版10532界面兴起“酷黑”风潮
-
Win10预览版10532的界面改动还是较为明显的，主要体现在右键菜单上面。总体来看，该版本的右键菜单间距更宽，视觉上更大气，操作上更便于触控。具体来说，任务栏右键菜单的变化最为明显。除了增加选项的宽...
- Win10预览版10532上手图集（windows10预览版下载）
-
IT之家讯8月28日，微软今天推送了Win10预览版10532快速版更新，在该版本中，微软主要是加强细节上调整，并且主要是增强Edge浏览器性能等。在Windows10预览版10532中，微软改进了...
- Win10预览版10532上手视频亮点演示
-
IT之家讯8月28日消息，今天凌晨微软向WindowsInsider快速通道用户推送了Win10预览版10532。在Windows10预览版10532中，微软改进了右键菜单，外观更加现代化。另外还...
- 第二篇 前端框架Vue.js（vue前端框架技术）
-
前端三大核心是网页开发的基础，Vue则是基于它们构建的“生产力工具”。通俗理解就是HTML是化妆的工具如眉笔，CSS是化妆品如口红，JavaScript是化妆后的互动，而Vue就是化妆助手。有了化妆工...
- 基于SpringBoot + vue2实现的旅游推荐管理系统
-
项目描述...
- 基于Vue以及iView组件的后端管理UI模板——iview-admin
-
介绍iView-admin是一套后端管理界面模板，基于Vue2.0，iView（现在为ViewUI）组件是一套完整的基于Vue的高质量组件库，虽然Github上有一套非常火的基于ElementUI...
- 别再说你会SPA开发了，这5个核心你真的搞懂了吗?
-
前言此spa非彼spa,不是你所熟知的spa。你所熟知的spa作者肯定是没有你熟悉的。我们这里指的是在前端开发中的一种模型，叫作单页应用程序，顾名思义，就是整个项目只有一个页面，而页面中的内容是动态的...
- React.js Top20面试题（react.js中文官网）
-
概述作为React开发者，对框架的关键概念和原则有扎实的理解是很重要的。考虑到这一点，我整理了一份包含20个重要问题的清单，每个React开发者都应该知道，无论他们是在面试工作还是只是想提高技能。...
- 美媒:特朗普签署行政令后，FBI又发现约2400份、总计超14000页涉肯尼迪遇刺案文件
-
来源：环球时报新媒体1月23日特朗普下令公布肯尼迪遇刺案相关机密文件图源：美媒综合福克斯新闻网和Axios网站10日报道，在总统特朗普签署行政令，要求公布“肯尼迪遇刺案”相关政府机密文件之后，美国...
- 2021 年 Node.js 开发人员学习路线图
-
Node.js自发布以来，已成为业界重要破局者之一。Uber、Medium、PayPal和沃尔玛等大型企业，纷纷将技术栈转向Node.js。Node.js支持开发功能强大的应用，例如实时追踪...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
- 微软开始推送Win10预览版10532快速版更新
- Win10预览版10532更新内容大全（windows10更新预览版）
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
- Win10预览版10532界面兴起“酷黑”风潮
- Win10预览版10532上手图集（windows10预览版下载）
- Win10预览版10532上手视频亮点演示
- 第二篇 前端框架Vue.js（vue前端框架技术）
- 基于SpringBoot + vue2实现的旅游推荐管理系统
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)