【408数据结构与算法】—串和BF算法（二十四）
一、串的定义
串（String）：零个或多个任意字符组成的有限序列
❤️❤️串的几个术语
- 子串：串中任意个连续字符组成的子序列（含空串）称为该串的子串
- 真自串：是指不包含自身的所有子串
- 字符位置：字符在序列中的序号为该字符在串中的位置
- 子串位置：子串第一个字符在主串中的位置
- 空格串：有一个或多个空格组成的串，与空串不同
- 串相等：当且仅当两个串的长度相等并且各个对应的字符都相等时，这两个串才是相等的
- 所有的空窜是相等的
二、串的案例引入
串的应用非常广泛，计算机上的非数值处理对象大部分是字符串数据，例如文字编辑，符号处理，各种信息处理系统等等
🍑🍑例如：病毒感染检测
研究者将人的DNA和病毒的DNA均表示由一些字母组成的字符串序列
三、串的类型定义
四、串的存储结构以及运算
串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构
😛串的顺序存储结构
🤣串的链式存储结构
- 优点：操作方便
- 缺点：存储密度低
😅串的链式存储结构—块链结构
五、串的模式匹配算法
- 算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）
- 算法应用：搜索引擎，拼写检查、语言翻译、数据压缩
算法种类
- BF算法（Brute-Force又称古典的、经典的、朴树的、穷举的）
- KMP算法（特点：速度快）
Brute—Force简称为BF算法，亦称简单匹配算法，采用穷举法的思路
算法的思路：它是从每一个字符开始依次与T的字符进行匹配
🤣BF算法设计思想
Index（S，T，pos）
- 将主串的第pos个字符和模式串的第一个字符比较
- 若相等，继续逐个比较后续字符
- 若不等，从主串的下一字符起，重新与模式串的第一个字符比较
- 知道主串的一个连续子串字符序列与模式串相等，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0
BF算法的时间复杂度
