【408数据结构与算法】—串和BF算法（二十四）

【408数据结构与算法】—串和BF算法（二十四）

一、串的定义

串（String）：零个或多个任意字符组成的有限序列

❤️❤️串的几个术语

• 子串：串中任意个连续字符组成的子序列（含空串）称为该串的子串
• 真自串：是指不包含自身的所有子串
• 字符位置：字符在序列中的序号为该字符在串中的位置
• 子串位置：子串第一个字符在主串中的位置
• 空格串：有一个或多个空格组成的串，与空串不同
• 串相等：当且仅当两个串的长度相等并且各个对应的字符都相等时，这两个串才是相等的
• 所有的空窜是相等的

二、串的案例引入

串的应用非常广泛，计算机上的非数值处理对象大部分是字符串数据，例如文字编辑，符号处理，各种信息处理系统等等

🍑🍑例如：病毒感染检测
研究者将人的DNA和病毒的DNA均表示由一些字母组成的字符串序列

三、串的类型定义

四、串的存储结构以及运算

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构

😛串的顺序存储结构

🤣串的链式存储结构

• 优点：操作方便
• 缺点：存储密度低
  

😅串的链式存储结构—块链结构

五、串的模式匹配算法

1. 算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）
2. 算法应用：搜索引擎，拼写检查、语言翻译、数据压缩

算法种类

• BF算法（Brute-Force又称古典的、经典的、朴树的、穷举的）
• KMP算法（特点：速度快）

Brute—Force简称为BF算法，亦称简单匹配算法，采用穷举法的思路
算法的思路：它是从每一个字符开始依次与T的字符进行匹配

🤣BF算法设计思想

Index（S，T，pos）

• 将主串的第pos个字符和模式串的第一个字符比较
• 若相等，继续逐个比较后续字符
• 若不等，从主串的下一字符起，重新与模式串的第一个字符比较
• 知道主串的一个连续子串字符序列与模式串相等，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0
  

BF算法的时间复杂度