串匹配与KMP失配函数

考点定位

本课深化 串匹配与KMP失配函数。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

朴素匹配失配后回退主串；KMP利用模式串自身前后缀结构，只移动模式指针，使主串指针不回退。

算法推演

构造前缀函数π[i]：失配时沿π[j-1]回退，匹配则j加一；找到完整模式后将j回退到π[m-1]以允许重叠匹配。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

处理完文本前i个字符后，j是该前缀的最长后缀且也是模式前缀的长度。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：next、nextval和前缀函数定义下标不同，必须先确认教材约定。

随课应用

输入两行文本text和非空模式pattern，输出pattern在text中的出现次数，重叠出现也计数。使用Python 3。

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。