QOJ.ac

QOJ

As a traditional event in the past years, join the IOI 2026 Prediction Game!

Type: Editorial

Status: Open

Posted by: yangzichen1203

Posted at: 2026-07-23 21:26:07

Last updated: 2026-07-23 22:11:23

Back to Problem

子序列自动机。

先翻转字符串，求相邻前缀 $s[1:i]$ 中以 $i$ 结尾的子序列不为 $s[1:i-1]$ 子序列的最小长度的最大值。

设 $f_i$ 表示最早在 $i$ 位置完成匹配的子序列的最小长度，发现

$$f_i=1+\min_{j=pre_i}^{i-1}f_j$$

$$ans=\max_{i=1}^{n}f_i$$

可以用单调栈维护 $pre$，时间复杂度 $O(n)$。

No comments yet.