# 疯狂的串串：区间内的 KMP 匹配

出题人解法：截取查询区间，反复查找模式串，并将下次起点只前移一位。Codex（GPT-6）：应用已有的 KMP 算法，给出每次查询的线性时间界及重叠匹配证明。

## 首选方案

对当前模式串 $t$ 构建前缀函数 $\pi$ . $\pi_i$ 表示 $t_0\ldots t_i$ 的最长真前缀、同时也是其后缀的长度。

从 $S_{l-1}$ 开始扫描到 $S_{r-1}$ ，这里已经转为零起始下标。维护已匹配长度 $j$ ，初始为零。新字符与 $t_j$ 不同时，沿 $j\gets\pi_{j-1}$ 回退；相同时将 $j$ 加一。若 $j=|t|$ ，记录一次匹配，然后令 $j\gets\pi_{j-1}$ ，继续扫描。

匹配成功后回到最长真边界，而不是清零，才能保留重叠。例如 `aaa` 在 `aaaaa` 中依次得到三个不同起点。每次查询从零状态开始，扫描范围不超过区间端点，不会把跨出区间的匹配计入。

## 正确性

前缀函数列出每个前缀所有可能的更短边界链。失配时，已经匹配的后缀若仍可能成为新匹配的前缀，其长度必须属于这条链；按链回退不会漏掉候选。匹配时延长一个字符保持该性质。当长度达到模式长时，恰好发现一个完整出现；回退到最长真边界保留所有可继续延长的重叠可能性。

扫描每个区间字符一次，每个出现恰在读入其最后一个字符时计数，终点不同与起点不同一一对应。扫描只从区间左端点开始且在右端点结束，因此计数对象恰为完全包含在区间中的出现。

## 复杂度与比较

令 $q=r-l+1$ 、$L=|t|$ . 构建前缀函数为 $O(L)$ ；匹配长度总增量至多 $q$ ，回退次数受此前增量限制，扫描为 $O(q)$ . 单次查询时间为 $O(q+L)$ ，除保存 $S$ 以外使用 $O(L)$ 空间。若 $N=|S|$ 、$L_{\max}$ 为最长模式长度，总时间为 $O(N+M(N+L_{\max}))$ ，空间为 $O(N+L_{\max})$ .

程序见 [std.cpp](std.cpp)。[逐起点查找](solution-alternative.zh.md)与 [alternative.cpp](alternative.cpp)保留出题人的字符串库方法，代码短、直观，作为备用方案，也通过完整数据。按逐字符比较分析，其查询时间上界为 $O(qL)$ ，常数及实际速度依赖字符串库。首选 KMP 的依据是显式的线性最坏时间界，不把库函数实测时间等同于其理论最坏情形。

测试覆盖重叠、长模式、近似匹配后失败、周期串、区间边界和无匹配，见 [plan.json](tests/plan.json)及[评测说明](../../../docs/评测环境与性能.md)。