# 吃糖果题解

## 解法比较

出题人解法将所有模式串放入 AC 自动机，沿失配链接继承“存在匹配结尾”的标记。扫描主串时，一旦出现匹配就计入答案并回到根，保证下一段从已选片段之后开始。最早结束的片段可替换任何最优方案的首段而不影响后续选择；下文给出交换证明。

Codex（GPT-6）的实现使用数组下标表示自动机节点。设模式总长为 $S$ 、主串长为 $L$ ，时间为 $O(S+L)$ ，存储自动机与输入共需 $O(S+L)$ 空间。

## 思路

把所有被选择的片段按右端点从小到大排序。对于当前尚未使用的后缀，选择**最早结束**的可用片段是最优的：若某个最优方案的第一段结束得更晚，用最早结束的片段替换它，不会挡住后续片段。反复替换即可得到贪心策略。

扫描 $T$ 时，只要从上次选择的片段之后开始的某个模式串在当前位置结束，就立即选择一段，并重新开始匹配。此时不必区分匹配的是哪个模式串，因为它们的结束位置相同。

## 用 AC 自动机找出最早的结束位置

把所有 $P_i$ 插入二进制 Trie，并构造失配边。一个状态若自身是模式串终点，或者其失配祖先是模式串终点，就标记为终点状态。扫描 $T$ 时，每读入一位沿自动机转移；遇到终点状态就把答案加一，并把状态重置为根节点，表示下一段只能从当前位置之后开始。

重置后无法匹配跨越已选择片段的模式串，正好符合区间不能重叠的要求。$n=0$ 时自动机只有根节点，答案为 $0$ .

## 正确性

设贪心第一次选择的片段在位置 $r$ 结束。任何可行方案的第一段都不会早于 $r$ 结束。把一个最优方案的第一段替换成贪心片段后，后续片段仍从大于 $r$ 的位置开始，因而仍可行且段数不变。对剩余后缀重复同样论证，贪心段数就是最优值。

自动机的终点标记覆盖了当前状态和全部失配祖先中的模式串终点，因此它恰好在某个模式串于当前位置结束时触发。重置状态保证接下来选出的片段与此前片段不相交，所以程序实现了上述贪心策略。

## 复杂度

设 $S=\sum |P_i|$ 、$L=|T|$ . 建树、构造失配边与扫描的总时间为 $O(S+L)$ . 自动机及其构造队列占用 $O(S+1)$ 空间；标准程序还保存了长度为 $L$ 的主串，因此实际总空间为 $O(S+L)$ .