CF461E

SoyTony · 2023-10-01 16:55:00 · 题解

在 s 中添加一个字符串使得操作次数增加意味着添加的部分没有出现在 t 中，使操作次数尽量多意味着这样的未出现子串是极短的，也就是删去最后一个字符后是出现 t 中的。

构造的过程实际是在原串 s 的基础上增加一个子串得到 s'，其中 s 的末尾字符 c_1，s' 的末尾字符 c_2，增加的部分是以 c_1 开头 c_2 结尾且最短的未在 t 中出现的字符串（不包含 c_1），因此增加的部分按开头结尾分类取最短有关，也就是 4\times 4=16 种。容易发现这些字符串长度是 O(\log_4 |t|) 的。

这样得到一个 O(|t|\log_4 |t|\log_2 |t|) 预处理（使用哈希以及 map 判断当前长度的所有字符串是否都已经出现），DP 复杂度 O(n\log_4 |t|) 的做法。注意最后形成的 s 的末尾未必是一个 t 不包含子串的末尾，也可能是补齐了一个后缀，例如 \texttt{AADACABBABDBCCACBCDDADBDC} 中所有长度为 2 的字符串都已经出现，若构造出长度小于 n=4 的 \texttt{ABC}，可以添加为 \texttt{ABCD}，而 \texttt{CD} 在 t 中是出现过的。

考虑优化，由于长度很小，直接拆成若干长度为 1 的边，变成朴素的游走 n 步问题，贡献只在最后一条边产生，矩阵快速幂即可解决。统计答案也要考虑上面的情况。

时间复杂度 O(|t|\log_4 |t|\log_2 |t|+(|\Sigma|^2\log_4 |t|)^3\log_2 n)。

提交记录：Submission - CodeForces