一、串的存储结构

串有三种存储结构。分别是：定长顺序存储、堆分配存储表示和块链存储表示

• 定长顺序存储，即定长数组，用来一组连续的存储单元存储串的字符序列。串的长度如何表示？
  ①如同数据结构中定义一样，用一个额外变量length存放串的实际长度。 ②在串值的最后面加入一个不计串长的“\0”表示串结束，此时串长隐含（需要固定算法计算）。
• 堆分配存储表示，仍是一组连续的存储的单元，作为自由存储区——堆，通过malloc和free完成内存动态存储。若malloc分配成功，会返回一个指向起始地址的指针，作为串的基地址，这个串由ch指针来指示；若分配失败，返回null。
  
• 块链存储表示（上述两个为高级程序设计语言所采用），串的字符序列采用链表存储，为了提高存储密度，通常每个节点存储多个字符，一个节点存放不满时通常用“#”填充，节点大小即为存放字符的数量。

二、串的模式匹配-找主串中是否包含模式串

重点关注：KMP和暴力模式匹配的复杂度、KMP主串和模式串指针的变化（会不会变小？变化公式？）、给模式串求next，nextval数组、nextval为什么这样优化、滑动距离如何计算、字符比较次数（移动后一些不需要比较）
模式串：你希望在大串中找到的小串
主串：大串

1.简单匹配算法：

暴力循环，产生了很多回溯（针对模式串说的，内存中发生变化的指针经常返回到模式串首字符，重新对比，这里强调这种指针前移造成了很多无意义的比较，所以说产生回溯）。最坏时间复杂度为O（nm），n和m分别为主串和模式串的长度。

2.改进的模式匹配算法——KMP

避免了简单匹配算法主串指针经常出现回溯现象导致的开销问题。没有回溯现象。
几个概念。前缀是不包含本身，以首字母开头的所有字符串；后缀是指不包含本身，以尾字母结尾的所有字符串；部分匹配值是字符串的前缀和后缀的最长相等前后缀长度。KMP算法时间复杂度为O（m+n）

KMP算法的模拟步骤： // 其实比较麻烦。正常都是手算步骤
①计算模式串的部分匹配值
②写出PM表（部分匹配值表）
③按公式右滑
举例：
①计算部分匹配值。假设“ababa”
②写出PM表，假设已知“abcac”的部分匹配值为00010

③按公式右滑。

求next数组，next[ j ]的含义是：下一次从哪里开始比。next[1] = 0，next[2]=1，是固定不变的（若题目规定从0开始编号，则分别为-1，0，所有的next数组值相差1）。
只要给出模式串，就能得到next数组。计算方法：next[ j ] = j-1个字符串的部分匹配值：当主串与模式串进行比较，模式串的第j个位置失配时，应找前j-1个字符串的部分匹配值（也是前后缀相同时它们最大的长度），然后将前缀移到后缀的位置上。

KMP算法的手算步骤（根据模式串，算出next数组）：
①next前两位直接置0,1，发现不对再改0（注意下标是从0开始还是从1开始，其实差1，都一样）
②初值为1，当前为匹配失败，看前面的最大前后缀的长度，加1后为当前next[ j ]的值（需要右滑滑动的位数 = j-next[j]，本质就是手算步骤③中的公式）

3，KMP算法的进一步优化：

当模式串中出现很多重复的字符时，根据next数组匹配的KMP算法就会进行很多无意义的比较。于是将next数组改进为nextval数组，这样就优化了这个问题。
求nextval数组（继承的思想）：前面两个不变。第二个有可能也要变，见下tips3-9。在第j的位置，如果对应字符与next[j]位置上的字符不同，就不用修改；如果相同就要继承。

1. KMP算法在进行模式匹配时，指示主串的指针不会变小，而指示模式串的指针可能会变小。但尽管如此，仍然称KMP避免了回溯现象：虽然模式串的指针也会前移，但它根据PM表跳过了那些重复对比的地方，所以比较都是必要的，没有产生开销，所以没有产生回溯。
   算法中i为主串的指针，j为模式串的指针。当发生失配时，i不变，j变成next[ j ]
2. 注意KMP模式匹配时移动后哪些字符需要对比，哪些不需要对比。右滑后，从上次对比主串失败的地方开始算（包括该地方）
3. 体会nextval的优化之处。模拟两者的流程。
   
   
4. 题中没说下标从哪开始，直接假设从1开始，计算next数组。右滑距离（j - next[ j ]）是不变的（因为从0开始，j会减去1，next[j]也会减去1）。
5. 实际上KMP算法本质上不会移动字符串，本质上是指针的变化。这里只是为了演示教学方便。