增量构造+答案上界推出增量构造上界确定复杂度：CF1063F

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135129285

https://www.luogu.com.cn/problem/CF1063F

可以贪心一波， $t$ 长度必然是 $ans,ans-1,ans-2,ans-3,\dots,3,2,1$ 这样子。

如果一个 $k$ 不存在，则显然 $k+1$ 不能存在。在满足这种情况下，要么二分，要么增量构造。这题显然不是二分，于是我们考虑增量构造。

考虑暴力。假设当前构造的是 $k$ ，显然从后往前，我们记 $f_i$ 表示从 $i$ 开始的后缀是否可行， $g_i$ 是上一层的答案。我们直接把后面不交的长为 $k-1$ 的串，然后判断 $s[i:i+k-2]$ 或 $s[i+1:i+k-1]$ 是否存在即可。

考虑优化。我们先分析一波复杂度。答案上界为 $2\sqrt n$ ，复杂度 $O(2n\sqrt n)$ ，那我们干脆不优化了。（虽然可以优化到 $O(n)$ ，留给读者自证）