数据结构（九）串

定义

零个或者多个字符组成的有限序列

串的比较

大小

串的抽象数据类型

串的顺序存储结构

串的顺序存储结构是用一组连续的存储单元来存储串中的字符序列的。

串的代码实现

链串的存储结构

优点：存储方便
缺点：储存密度低（存储密度=串值所占的存储位/实际分配的存储位置）

BF（Brute-Force）算法

时间复杂度O(n*m)

主要思路

从目标串 T 的的第一个字符起与模式串 P 的第一个字符比较。若相等，则继续对字符进行后续的比较；否则目标串从第二个字符起与模式串的第一个字符重新比较。直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

KMP 算法

时间复杂度O(n+m)

KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数，以达到快速匹配的目的。每趟匹配过程中出现字符串比较不等时，不回溯主指针 i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的距离，继续进行比较。

前缀：指除了最后一个字符外，一个字符的全部头部组合。
后缀：指除了第一个字符外，一个字符串的全部尾部组合。

next 数组的代码实现（部分分配值）

参考

【1】字符串匹配的KMP算法@阮一峰
【2】字符串 模式匹配