吃糖果题解¶
解法比较¶
出题人解法将所有模式串放入 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)\) .