字符串（串）
串(string)是由零个和多个字符组成的有限序列，一般记为：
前缀：字符串的前缀指除了最后一个字符之外的所有头部子串（是一个集合）。例如，字符串’abcde’的前缀是{a, ab, abc, abcd}，字符串’a’的前缀是{}。\
后缀：字符串的后缀指除了第一个地租之外的所有尾部子串。例如，字符串’abcde’的后缀是{e, de, cde, bcde}，字符串’a’的后缀是{}。\
部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。例如，字符串’abcde’的部分匹配值为0，因为不存在前缀和后缀相等的情况。
串的存储结构
- 定长顺序存储表示
- 堆分配存储表示
- 块链存储表示：类似于线性表的链式存储结构，每个结点称为块，所以链表称为块链结构。和线性表的链式存储结构不同的是，每个块可以存储多个字符。
串的模式匹配
串的模式匹配：子串的定位操作，它通常求的是子串（substring），也称为模式串，在主串中的位置。
暴力匹配法
双重循环，假设主串长度为$n$，模式串长度为$m$，暴力匹配法时间复杂度为$O(mn)$。
KMP算法
KMP算法分为两部分：
- 计算模式串$T$的错位部分匹配值数组$next$。
- KMP匹配算法。