题解

思路

先列出 $t$ 在原串中的所有起始位置。选择一次出现会消除所有与它区间相交的出现，因此问题变成：用最少的等长区间支配全部区间，并统计最优选择集合。

做法

设出现位置为 $p_0<p_1<\cdots<p_{k-1}$，$m=|t|$。令 $dp_i$ 和 $ways_i$ 表示从第 $i$ 个尚未消除的出现开始所需的最少选择数及方案数。

为了消除左端点为 $p_i$ 的出现，本次可以选择任意满足 $p_j-p_i<m$ 的 $j\ge i$。选择 $j$ 会破坏所有与它重叠的出现；同时，后续还能被选择的出现必须与它不相交。因此下一状态是第一个满足 $p_h-p_j\ge m$ 的下标 $h$。用 $1+dp_h$ 更新，并在相同最优值时累加方案数。没有出现时答案为 $0,1$。这一跳转同时保证了最终选择集合中的区间两两不重叠，符合替换后的字符串语义。

子任务一枚举出现位置的全部子集并检查是否覆盖所有出现。子任务二中 $|t|=1$，不同出现互不重叠，必须全部选择，方案唯一。

复杂度

出现位置至多 $|s|$ 个。动态规划时间复杂度为 $O(|s|^2)$，空间复杂度为 $O(|s|)$。