题解

思路

若希望第 $i$ 个与第 $i+1$ 个匹配位置间隔尽量大，前 $i$ 个字符应尽量靠左匹配，后 $m-i$ 个字符应尽量靠右匹配。这两个极端嵌入可各用一次贪心扫描求出。

做法

从左向右扫描 $s$，依次匹配 $t$，记录 left[i] 为 $t_i$ 能取得的最早位置。从右向左同理记录 right[i] 为 $t_i$ 能取得的最晚位置。

枚举 $0\le i<m-1$，把前缀按最早方式匹配到 left[i]，把后缀按最晚方式从 right[i+1] 开始，候选宽度为 right[i+1]-left[i]。取最大值。

正确性证明

对任意美丽序列及切分 $i$，其第 $i$ 个位置不可能早于 left[i]，第 $i+1$ 个位置不可能晚于 right[i+1]，所以该间隔不超过算法候选值。另一方面，最早前缀嵌入与最晚后缀嵌入都合法；由于题目保证完整子序列存在，有 left[i]<right[i+1]，两段可以拼成一个美丽序列并达到该候选间隔。因此每个切分的最大值都被精确计算，所有切分取最大即为答案。

复杂度分析

时间复杂度为 $O(n+m)$，空间复杂度为 $O(m)$。

子任务说明

• $n\le20$ 时枚举全部位置组合。
• $n\le3000$ 时对每个切分重新扫描两端嵌入，复杂度为 $O(nm)$。
• 满数据预处理最早前缀与最晚后缀位置。