串

串是由零个或多个字符组成的有限序列，又名叫字符串。
串中的字符数目n称为串的长度，
零个字符的串称为空串，可以直接用“”表示，也可以用希腊字母 Φ。

• 串的比较

图片.png

• 串的抽象数据类型

图片.png

• 串的存储结构

  • 串的顺序存储结构
    串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列。
    这样会导致很多截断，是存储的空间不足的原因
    于是对于串的顺序存储，串值的存储空间可在程序执行过程中分配而得，比如在计算机中存放一个自由存储区，叫做“堆”。这个堆可由c语言的动态分配函数malloc（）和free（）来管理。
  • 串的链式存储结构
    对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性。结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此一个结点可以存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全。

图片.png

具体几个字符合适，看情况
但是除了连接串和串操作时一些方便外，总个来说不如顺序存储灵活，性能也比不上。

• 朴素的模式匹配算法

  • 字串在串中的定位操作通常被称为串的模式匹配。

依次进行，匹配到为止，时间复杂度是O（n+m），最复杂的情况是O（n-m+1）*m。

• ＫＭＰ模式匹配算法

  • KMP模式算法的原理
    其实就是靠一些数学个规律，使算法不用按主串与字串的顺序一个个匹配，这样字串会一直重复匹配一些类似的东西，引入next数组值，可以通过回溯j的一些规律来减少字串的匹配重复。

• next数组值推导

• KMP模式匹配算法实现

• KMP模式匹配算法改进