这章在大纲中是查找的一部分，考察的内容也比较少

4.1 串定义与基本操作

4.1.1 定义

4.1.2 基本操作

求子串

比较

定位

字符集编码

4.1.3 存储结构

顺序存储

链式存储

4.2 模式匹配

在主串中寻找模式串相同的子串，并返回位置

4.2.1 朴素模式匹配算法（暴力）

与index算法相同，下面使用另一种方式实现： 这种算法的思想和滑动窗口有点相似

4.2.2 KMP算法

朴素算法出现不匹配的位置的前面的主串字符的内容是已知的

也就是说，在第n个字符匹配失败的时候，仅仅根据模式串的内容就可以确定j指针指向的位置，这与主串无关。对于模式串‘abaabc’：

获得n与j之间的对应关系（next数组），主串的指针就不会回溯，可以大大的提升效率

性能对比

求next数组（手算）

换言之，无脑写next[1]=0，next[2]=1，剩下的部分分析

求nextval数组（优化next数组）

在这种情况下，i所指的字符一定不是a，j在移动到1后（a），一定会匹配失败

我们可以直接将next[3]的值改为0，跳过匹配失败的那一步：

nextval[1]无脑写0，只有匹配失败的字符和其next数组的字符相同时，才会优化：