3月板刷ARC记录

ARC058F

考虑背包，记 \(f_{i,j}\) 表示考虑前 \(i\) 个串，取出长为 \(j\) 的最小串。

由于涉及字典序比较，时间复杂度为 \(\mathcal O(nk^2)\)。

字典序比较不同于计算式比较，找到 \(LCP\) 后第一位即可得出结果。

考虑仅保留能转移到 \(f_{n,k}\) 的 \(f_{i,j}\)。

对于 \(f_{i,j1},f_{i,j2}(j1<j2)\)，若 \(f_{i,j1}\) 不是 \(f_{i,j2}\) 的前缀，则若前者小于后者，那么前者优于后者，否则后者优于前者。

这样对于 \(f_{i,*}\)，能推到答案的一定是 \(f_{i,\max j}\) 的前缀，我们保留这个最长串即可做到空间 \(\mathcal O(nk)\)。

考虑 \(f_{i,j}\) 仅由 \(f_{i-1,j}\) 和 \(f_{i-1,j-len}\) 得出，可以 \(\mathcal O(\log n)\) 比较字典序得出大小关系。

时间复杂度 \(\mathcal O(nk\log k)\)，发现比较字典序的方式类似一个串与另一个串的某个后缀的 \(LCP\)，使用 \(Z\) 算法，即可做到 \(\mathcal O(nk)\)。