| 8.8 | 113-120页：第四章 串next数组的公式推导+KMP算法的优化 |
|---|
summary 第三章
在考试中，栈或队列都是作为一个工具来解决其他问题的，我们可以把或队列的声明和操作写得很简单，而不必分函数写出。以顺序栈的操作为例：
- 声明一个栈并初始化
ElemType stack[MaxSize]; int top = -1;
- 元素进栈
stack[top++] = x;
- 元素x出栈
x = stack[top--];
对于链栈，同样只需要定义一个结构体，然后从讲解中摘取必要的语句组合在自己的函数代码中即可。顺序栈考的比较多！！
第四章 串
本章主要掌握字符串模式匹配，重点掌握KMP匹配算法的原理及next数组的推理过程，手工求next数组可以先计算出部分匹配值表然后变形，或根据公式来求。了解nextval数组的求解方法。
4.1串的定义和实现 直接跳过，从4.2串的模式匹配开始
背完这章是不是就不想吃串串了
文字内容
问
- 什么是串的模式匹配？
- 暴力匹配效率低的原因？
- 对暴力匹配的改进是什么算法？从哪些地方开始着手的？
- 什么是前缀、后缀和部分匹配值(PM)？（–>服务于 怎么计算字符串的部分匹配值【应用】—>next数组的求法）
- 部分匹配值的作用？（—>核心理解公式的含义）
- next数组与PM数组的关系？
- next数组中的第一个元素，和最后一位元素是怎么处理的？原因是什么？
- 当next数组中的元素加一后，next[j]的含义是什么？
- 如何推理next数组的一般公式？
- 设主串为’s1s2…sn’，模式串为’p1p2…pm’，当主串中第i个字符与模式串中第j个字符失配时，子串应该向右滑动多远，然后与模式串中的哪个字符比较？
- KMP算法的原理是什么？
答
- 子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串的位置。
- 在暴力匹配中，每趟匹配失败都是模式串后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式串的某个前缀（电子130图4.2的第三趟匹配），这种频繁的重复比较相当于模式串不断地自我比较（第四、五趟），这就是其效率低的原因。
- KMP算法。可以从分析模式串本身的结构着手，若已匹配相等的前缀序列（主串中の）中有某个后缀（这段被匹配相等中的后面几个）正好是模式串的前缀，则可以将模式串向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并从该位置开始继续比较。而模式串向后滑动位数的计算仅与模式串本身的结构有关，而与主串无关。
- 前缀指除最后一个字符以外，字符串的所有头部子串；后缀指除第一个字符外，字符串的所有尾部子串；部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度（PM表和主串无关）。
- 先写出PM表也就是部分匹配值的表；在匹配过程中遇到不匹配情况时，主串中的下标i的移动位数 = 已匹配字符数 - 对应的部分匹配值；然后再开始下一趟匹配。
书上： 某趟发生失配时（你是会缩写的），若对应的部分匹配值为0，则表示已匹配相等序列中没有相等的前后缀，此时移动的位数最大，直接将子串首字符后移到主串当前位置进行下一趟比较；若已匹配相等序列中存在最大相等前后缀（可理解为首尾重合），则将子串向右滑动到和该相等前后缀对齐，然后从主串当前位置进行下一趟比较。 - 使用PM表时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来不方便，所以将PM表右移一位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可，这样也就是next数组。
此时move = j -1 -next[j]。
此时j应回退到：j = j - move = j - j + 1 + next[j] = next[j] + 1
如果为了计算方便next数组中的数++
此时j = next[j] 表示： j回退到next[j]的位置
- next数组中，缺失的第一位元素使用-1来填充，是因为如果第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数；
最后一位元素在右移的过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，所以可以舍去。 - 当子串的第j个字符与主串发生失配时，跳到子串的next[j]位置重新与主串当前位置进行比较。
挖
- 简单/暴力匹配算法的最坏时间复杂度为O(mn)，其中n和m分别为【】。
空
- 主串和模式串的长度
选择（仅错题）
【错误选项】
【思路】
【补充】不一定需要
代码内容
简单的模式匹配算法algorithm
使用定长顺序结构，是一种不依赖于其他串操作的暴力匹配算法。
下标从1开始存储主串和模式串。
int Index(SString S , SString T){int i = 1 , j = 1;while(i <= S.length && j <= T.length){if(S.ch[i] == T.ch[j]){i++;j++;}else{i = i-j+2;j=1;//这一步是为了将 i 移动到下一个开始匹配的位置。}if(j>T.length) return i-T.length;//说明模式串被遍历了一遍，是子串，开始位置推的时候记得i执行了i++的语句！！！else return 0;}
}
如果不记得i更新的公式，自己推，反正i要退回到它本次匹配失败的 开始匹配位置(i-j+1) 的 下一个位置所以是i-j+2。
