疯狂的串串：区间内的 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。逐起点查找与 alternative.cpp保留出题人的字符串库方法，代码短、直观，作为备用方案，也通过完整数据。按逐字符比较分析，其查询时间上界为 \(O(qL)\) ，常数及实际速度依赖字符串库。首选 KMP 的依据是显式的线性最坏时间界，不把库函数实测时间等同于其理论最坏情形。