Chapter 5 String

第 5 章串

串（string）是由零个或多个字符串组成的有限序列，又叫字符串。

零个字符的串称为空串（null string），长度为0；

串的比较

实际上是比较串的每个字符的ASCLL码值，例：字典中的英文排序。

串的存储结构与线性表相投，分为两种

用一组地址连续的存储单元来存储串中的字符序列的

类似线性表的链式存储，只不过一个结点数据类型变成了字符；

后续将结点数据类型改成了多个字符，一次存储，若最后一个结点未被占满时，可以用“#”或其他非串值字符补全。

在文本中对字符串字串的定位操作：串的模式匹配

简单地说：就是对主串的每一个字符作为字串开头，与要匹配的字符串进行匹配，对主串做大循环，对每个字符开头做的T长度的小循环，直到匹配成功或全部遍历完成为止。

可以避免大量的重复判断，将先前已经判断过的结果存储起来。

KMP模式匹配算法：避免不必要的回溯

在需要查找字符串前，先对要查找的字符串做一个分析，这样可以大大减少我们查找的难度，提高查找的速度。

（i：主串指针；j：子串指针）

精髓：i 永远不减；

可以更大程度减少多余的判断

next数组 && nextval数组

Last updated 5 months ago