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

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

取子串 \(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 则显式维护可复用前缀，提供更清楚的最坏时间界。