KMP 前缀函数与匹配计数

本节进入 408 强化阶段的 KMP 前缀函数与匹配计数。要求从定义出发完成真题级推演，并把过程写到可以复查。

状态模型与不变量

前缀函数 pi[i] 是模式串前缀中、同时也是 s[0..i] 后缀的最长真前缀长度；匹配时失配指针沿 pi 链回退。

开始计算前先列出输入、单位、下标与初始状态。算法题必须说明数据结构保存什么；硬件、操作系统和网络题必须画出字段或时间线。任何一步状态更新都要能指出依据。

例题推演

文本 aaaaa、模式 aaa 的匹配起点为 0、1、2，共 3 次，重叠匹配不能漏掉。

正式作答时按“公式或规则—代入—中间状态—结论”书写。若有多次访问、调度或转发，用表格逐行记录，不能靠脑中跳步。完成后用极小输入、边界输入和一个反例复核。

易错边界

找到一次匹配后把状态清零会漏掉重叠出现；必须回退到 pi[m-1]。

选择题要逐项检查前提与量词；计算题要检查字节/比特、周期/秒、地址/块号等单位；算法题还要说明最坏复杂度、额外空间和终止性。

随课训练要求

1. 单选题必须解释另外三项为何错误。
2. 多选题漏选、多选均不得分。
3. 计算题保留推导；代码题必须通过四个独立用例，禁止样例硬编码。
4. 将错因标为知识、建模、状态更新、计算或审题，并在次日重做。

能得到一个数不等于掌握；能重建状态、解释规则并迁移到变式才算完成。