首先我们可以说明，一定存在一个最优方案，使得最后一个串的右端点是 \(n\)。因为如果不是 \(n\)，那么可以往后扩展一个，或者整体前移一位之后再往后扩展一位。
然后我们可以说明，如果后缀 \([i,n]\) 存在一种方案使得其是最后一个，那么 \([j,n](j>n)\) 也存在一种方案。
所以我们可以二分一个 \(mid\)，然后 check \(mid\) 可不可行。
设当前区间为 \([l,r]\)，那么每次就是 \(l\) 往前移动一位，\(r\) 往前移动 \(2\) 位，当 \(l=1\) 的时候说明不可行。
如果当前区间 \([l,r]\) 之后存在一个与其相同的串，那么就可以跳到后面去，同时我们发现，跳到后面去一定比继续往前走更优，因为如果跳到后面去，那么走到前面的时候一定更短，那么前面往后跳的话也一定能跳。
那么这个二分的 check 就是 \(O(n)\) 的。预处理可以建立 SAM 找到每个后缀和后面的后缀的 LCP 最大值，总复杂度 \(O(n\log n+n|\Sigma|)\)。
等下，这个二分真的有必要吗？在位置 \(i\)，若长度 $\leq $ LCP 最大值，则这些长度一定可以循环跳完，那么对于位置 \(i\)，其能跳的最长串也就确定了，可以 \(O(n)\) 求出，复杂度 \(O(n|\Sigma|)\)。
标签：LNOI2022,二分,那么,后缀,可以,mid,P8368,后面 From： https://www.cnblogs.com/275307894a/p/17961640