Masha 的记忆片段 题解

思路

直接枚举所有可能片段会遇到 $O(m^2)$ 种目标子串。关键观察是：任何长度至少为 $4$ 的片段都能继续拆成长度为 $2$ 和 $3$ 的片段。偶数长度全部拆成若干个 $2$；奇数长度先取一个 $3$，其余拆成 $2$。因此，只要存在合法方案，就一定存在一个只使用长度 $2$ 或 $3$ 的方案。

这给出三个真实算法层级：

1. 当 $m\le18$ 时，可以枚举所有由长度至少为 $2$ 的段组成的划分，并逐段在已知号码中朴素查找。
2. 当 $n\cdot m\le4000$ 时，可以对目标串位置做动态规划，对每个可达位置枚举所有结束位置，再在全部已知号码中朴素查找对应子串。
3. 满规模时，只预处理所有长度为 $2$、$3$ 的已知子串，并对目标串做线性动态规划。

做法

预处理两个映射。对于每个已知号码和每个起点，记录长度为 $2$ 与长度为 $3$ 的子串各自的一次出现位置 $(l,r,i)$。

令 dp[x] 表示目标串前 $x$ 位是否可以被合法拼出，初始 dp[0]=true。从左到右扫描每个可达位置 $x$：

• 若 $s[x..x+1]$ 在长度 $2$ 的映射中出现，则转移到 $x+2$；
• 若 $s[x..x+2]$ 在长度 $3$ 的映射中出现，则转移到 $x+3$。

转移时记录前驱位置以及采用的已知子串。若 dp[m] 为假则无解；否则沿前驱从 $m$ 回溯至 $0$，反转后输出。

正确性来自两点：每次转移所记录的片段确实来自某个已知号码，所以回溯结果一定合法；反之，任意合法划分都可进一步拆成长度 $2$、$3$ 的片段，动态规划会枚举这些片段，因此不会漏掉可行方案。

复杂度

每组数据预处理耗时 $O(nm)$，动态规划耗时 $O(m)$，空间复杂度为 $O(nm+m)$（存储输入）或除输入外 $O(m+10^3)$。全部测试组的总时间复杂度为 $O(\sum n m)$。