题解：P15650 [省选联考 2026] 摩卡串 / string

_Communist · 2026-03-07 16:19:47 · 题解

感觉小于 T1，但是场上只写了 75。/ll

数据范围不太像贪心构造 Ad-hoc 之类，考虑 dp。

考虑如何计算在一个串 t 末尾加入一个字符的贡献。首先考虑不加入这个字符就已经确定 <s 的后缀，不管加入任何字符都会产生贡献。然后考虑等于 s 某个前缀的后缀，如果在 s 中对应下一位是 1，加入 0 之后会变成 <s 的后缀，带来贡献。

于是有 dp_{i,j,x,0/1} 表示当前串 t 末尾最长有 i 位等于 s[1:i]，有 j 个后缀已经确定 <s，t 有 x 个子串 <s，s 是否是 t 的子串 时 t 的最短长度。

转移考虑枚举在末尾加入 0/1，可以用 kmp 自动机维护 i 这一维，并且预处理出所有的贡献来计算新的 j,x。

直接做是 O(nk^2)（考场上写的这个），但是分析一下 j 的上界在 O(\sqrt k) 级别，所以可以做到 O(nk\sqrt k)。