Anthem of Berland 题解

思路

处理字符串从左到右时，只需保留当前后缀与 $t$ 的最长前缀匹配长度。这个状态正是 KMP 自动机的状态；每当转移到完整的 $t$，答案增加一，并沿失配边回到最长 Border，从而正确保留重叠出现。

做法

子任务 1：枚举问号替换

问号不超过三个时，枚举每个问号的 $26$ 种字母，得到完整字符串后直接统计 $t$ 的出现次数，取最大值。

子任务 2：枚举出现位置集合

先判断每个起点单独形成一次 $t$ 是否可能。两个被选择的出现若重叠，则重叠区域对字符的要求必须一致。预处理所有起点之间的冲突关系后，枚举出现位置的子集，求没有冲突的最大集合。所有被选出现对固定字符都合法，且两两重叠要求一致，因此这样的集合恰好对应一种可行替换。

子任务 3：KMP 自动机动态规划

预处理状态 $j$ 读入每个字母后的新状态以及是否形成一次完整匹配。设 $dp_j$ 表示处理完当前前缀后、自动机处于状态 $j$ 时能得到的最大出现次数。

若当前字符固定，只执行对应的一条转移；若当前字符是问号，则枚举替换字母并更新下一层状态。完整匹配后把状态退回 $t$ 的最长 Border，因此所有允许重叠的出现都会被计数。最终所有状态中的最大值就是答案。

复杂度

设 $q$ 为问号数。子任务 1 的时间复杂度为 $O(26^q|s||t|)$；子任务 2 的时间复杂度为 $O(2^{|s|}|s|^2)$；满分做法的时间复杂度为 $O(26|s||t|)$，空间复杂度为 $O(26|t|)$。题目保证 $|s||t|\le 10^7$。