当前位置: 首页 > 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;//返回不匹配标志
}

http://www.lryc.cn/news/97968.html

相关文章:

  • hive 全量表、增量表、快照表、切片表和拉链表
  • 数据结构07:查找[C++][B树Btree]
  • 在CSDN学Golang云原生(Kubernetes集群管理)
  • WPF实战学习笔记18-优化设计TodoView
  • Python版day59
  • [SQL挖掘机] - 算术运算符
  • 机器学习基础 数据集、特征工程、特征预处理、特征选择 7.27
  • Sass 常用的功能!
  • chmod命令详细使用说明
  • ICC2如何计算Gate Count?
  • Qtday3作业
  • 全球程序员需要知道的50+网址,有多少你第一次听说?
  • Matlab中实现对一幅图上的局部区域进行放大
  • mysql-速成补充
  • 微信小程序,商城底部工具栏的实现
  • Lab———Git使用指北
  • ChatGPT的工作原理:从输入到输出
  • redis数据库与主从复制
  • js加载和长任务
  • 利用Stable diffusion Ai 制作艺术二维码超详细参数和教程
  • 【C语言课程设计】图书管理系统
  • 在 ArcGIS Pro 中使用 H3 创建蜂窝六边形
  • 创建Electron项目
  • Spring Boot实践一
  • 简单认识NoSQL的Redis配置与优化
  • 开发一个RISC-V上的操作系统(二)—— 系统引导程序(Bootloader)
  • Git安装与学习
  • 【Docker】docker中容器之间通信方式
  • 算法-归并排序-JAVA
  • Flask 进阶