# 疯狂的串串：逐起点查找

出题人解法：截取区间后反复使用 `string::find` . Codex（GPT-6）：C++17 整理与边界验证，保留重叠处理。程序为 [alternative.cpp](alternative.cpp)，作为[KMP](solution.zh.md)的备用方案，能通过完整数据。

取子串 $U=S_{l-1}\ldots S_{r-1}$ . 从起点零开始调用 `U.find(t, pos)` ；若返回某个位置 $p$ ，答案加一，下次从 $p+1$ 继续。若返回 `string::npos` ，查询结束。

查找返回不小于当前起点的最早出现。每次严格增加起点，因此不会重复计数，也不会漏掉更早的未计数位置。前移一位允许下一次出现与当前出现重叠；若错误地前移 $|t|$ 位，则 `aaa` 中的两个 `aa` 会漏算一次。先截取区间保证所有返回位置对应的完整模式均在区间内。

令 $q=|U|$ 、$L=|t|$ . 按每个候选起点至多比较 $L$ 个字符的模型，总比较量为 $O(qL)$ ；截取区间为 $O(q)$ ，两者合计仍为 $O(qL)$ ，因为 $L\ge1$ . 查询临时空间为 $O(q+L)$ ，加上原字符串后为 $O(|S|+L)$ . 具体库实现可以更快，这里不依赖库函数额外的线性保证。

本方案只需库函数便能表达“找出所有出现”，适合入门和验证。KMP 则显式维护可复用前缀，提供更清楚的最坏时间界。