串

发表于2024-08-01|更新于2026-06-10|Computer Basics

|浏览量:

串

串

串（字符串）：由零个或者多个字符组成的有限序列。
串值：双引号括起来的字符序列
串长：所包含的字符总数量
子串（substring）
子串序号（index）
串相等：长度相等且对应位置的字符也一样
串常量：只能读，不能写
串变量：可读可写
串在计算机中的存储方式
- 定长顺序存储表示
- 堆分配存储
- 块链存储（块的意思是每个结点存放不止一个字符）

串的模式匹配算法

模式匹配：子串在主串中的定位称为模式匹配或串匹配
Brute-Force模式匹配算法
- 匹配流程
- 代码
  BF算法代码
- 执行的复杂度为O(m+n)，最坏为O(m*n)。当遇到s=”001”,p=”00000000001”的串的时候，就会遇到最坏情况
KMP模式匹配算法
- 改进点：每当一趟匹配出现字符不相等时，主串指示器不用回溯，而利用已经得到的部分匹配的结果，将模式匹配器向右尽可能滑动一段距离后在继续比较
- 匹配流程
- 代码
  KMP算法代码
- 可以大大缩短匹配的次数
- 时间复杂度一定是O(m+n)
- 仅当模式与主串之间存在许多部分匹配的情况，才会比BF算法有明显的性能提升

文章作者: xhj

文章链接: https://hzhzxfs.github.io/2024/08/01/%E4%B8%B2/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 xhj的博客！

Computer Basics

相关推荐

设计模式学习笔记

创建型作用：如何创建对象 1 单例模式单例模式（Singleton）创建分为饿汉式和懒汉式，但是在开源项目中使用最多的主要有两种写法。 1.1 静态常量静态常量方式属于饿汉式，以静态变量的方式声明对象。这种单例模式在 Spring 中使用的比较多，举个例子，在 Spring 中对于 Bean 的名称生成有个类 AnnotationBeanNameGenerator 就是单例的。 1.2 双重检查机制双重检查机制（DCL）方式属于懒汉式。 123456789101112131415161718public class Singleton { private volatile static Singleton INSTANCE; private Singleton() {} public static Singleton getInstance() { if (INSTANCE == null) { synchronized (Singleton.class) {...

绪论O记号问题：随着问题规模的增长，计算成本是如何变化的？考虑的是计算成本的增长趋势分析：在问题规模足够大的情况下，计算成本如何变化：需要执行的基本操作次数T(n) 需要占用的存储单元数量S(n)，一般不考虑空间占用对于T(n)转为O(f(n)) 常系数可以忽略，低次项可以忽略 O复杂度计算基于悲观的角度判断代码的复杂度常数复杂度O(1)：不含转向（循环、调用、递归等），部分特例虽然含有循环、调用、递归等，但是需要考虑到实际情况才能确定。对数复杂度O(log n)：高效，复杂度无限接近常数多项式复杂度O(n^c)：界定为多项式的最高次项线性复杂度O(n) 指数复杂度O(c^n)：计算成本高 1234567void func(int n){ // n是正整数 int i = 1; while(i<=n)i*=2;}// 被嵌套的深层语句是i*=2；频率由i<=n决定，显然时间复杂度为O(log n) 冒泡排序观察：有序序列中，任意一对相邻元素顺序 / 无序序列中，存在一对相邻元素逆序 ...

线性表线性表定义：由n个数据元素组成的有限序列；原则上数据类型可以不一致，但存储类型可能会做出一定的限制特性: 除第一个元素外,其他元素只有一个直接前驱;除了最后一个元素,其他元素只有一个直接后继. 表示方式:顺序存储方式/链表存储方式顺序表定义:将线性表中的元素相继存放在一个连续的存储空间中,可以利用一维数组描述数据结构特性:所有元素的逻辑先后顺序和物理存放顺序一致 123456789101112131415161718192021const MAX_SIZE = 100// SQListA 顺序表的静态存储表示type SQListA struct{ data [MAX_SIZE]int64 length int}// SQListB 顺序表的动态存储表示type SQListB struct{ data *int64 length int}// Init_SQ 初始化顺序表func Init_SQ(list *SQListA) bool{ list.d...

图概念图：由顶点集合和顶点间的关系集合组成的一种数据结构有向图与无向图：在有向图中，顶点对(x,y)是有序的；无向图是无序的完全图：在有n个顶点的图有n(n-1)/2条边，即为完全无向图；有n(n-1)条边，即为完全有向图顶点的度：某一个顶点与其相关联的边的条数，有向图度是入度和出度之和生成树：一个连通图的生成树是其极小连通子图，包括图中所有顶点，包含n-1条边图的存储结构－邻接矩阵在图的邻接矩阵表示中，有一个记录仪各个顶点信息的顶点表，还要一个表示各个顶点之间关系的邻接矩阵网络的邻接矩阵邻接表邻接表是邻接矩阵的改进形式，需要把邻接矩阵的各行分别组织为一个单链表、无向图的邻接表：有向图的邻接表和逆邻接表：网络邻接表：图的遍历与连通性 DFS（深度优先搜索） BFS（广度优先搜索）连通分量和生成树极小连通子图（一棵生成树）广度优先生成树、深度优先生成树非连通无向图生成的生成树组将组成非连通图的森林最小生成树（MST）网络带权重的最小和的生成树 Prim算法：从顶点开始依次找最短边，然后相连 Kruskal算法...

输入输出（IO）管理

输入输出IO管理三种常见的设备接口类型字符设备（键盘鼠标、串口等）块设备（磁盘、磁带、光驱等）网络设备（以太网、无线等） IO管理概述IO控制方式阻塞IOWait：读数据时，进程进入等待状态，直到数据读取完成；写数据时，进程进入等待状态，直到设备完成数据写入非阻塞IODon't Wait：立即从读写系统调用返回，返回值成功传输字节数异步IOTell me later：读数据时，使用指针标记好数据缓存区，立即返回，稍后内核将填充缓冲区并通知用户；写数据时，使用指针标记好用户缓冲区，立即返回，稍后内核将处理数据并返回给用户。 IO软件层次结构设备 -> 设备控制器 -> 设备驱动 -> IO子系统 -> 内核 IO核心子系统IO调度概念高速缓存与缓冲区缓存：数据传输双方访问速度差距较大，引入的速度匹配中间层。磁盘缓存是磁盘扇区在内存中的缓冲区

数据通信原理

数据通信原理通信系统的基本组成通信三要素：信源：信息的发送者，是发出各种信息（文字、图片或者数据）的信息源信宿：信息的接受者载体：传送信息的媒体（信道）噪声的存在对通信产生不利影响通信系统的基本组成变换器：将信源发出的信息变为载体上看传输的格式反变换器：将载体上传输的信息变换成信宿可识别格式信道：信息可以单向传输的途径按传输类型分类：有线信道无线信道按传输方式分类：模拟信道数字信道信道带宽：信道可以不失真地传输信号的频率范围信道容量：信道在单位时间内可以传输的最大信号量数据传输速率（bps）：信道在单位时间内可以传输的最大比特数。差错率、误码率：出错/总数、与传输距离成正比由于噪声的影响和信道带宽的限制，信号可能发生失真调制/解调：利用模拟信道支持数据信息传输的技术调制：将数据信息变换成适合于模拟信道上传输的电磁波信号（数字->模拟）解调：将从模拟信道上收取的载波信号还原成数据信息（模拟->数字）调制解调器：具有调制、解调功能的通信设备调制方法调制依据：模拟信号的三...