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

ax_by_c · 2026-03-09 11:15:53 · 题解

差了一步，跳了。

考虑从前往后直接 dp。

由于需要处理匹配上个 kmp 自动机，然后考察以 border 前面位置为开头的子串的字典序贡献。

由于它们匹配不上所以贡献形式已经确定了，一定是每次 push_back 时不贡献或者一定贡献，border 部分贡献可以暴力预处理。

于是 f_{i,j,k,0/1} 表示当前 border 长度，当前字典序 <s 子串数，当前 border 之前一定贡献的开头个数，以及是否完整匹配过 s，时的最小长度。

注意到 j=O(k^2)，因此时间复杂度 O(nm^{\frac{3}{2}})。

没有心情写代码了。