题解

思路

若公共前缀长度为 $x$，则字符串前缀 $s[0..x-1]$ 必须在 $s$ 中出现至少 $k$ 次且这些出现两两不重叠。用 Z 函数可以常数判断从任一位置开始是否匹配此前缀，贪心选择最靠左的合法出现即可得到最多出现次数。

做法

$n\le100$ 时直接比较字符；$n\le3000$ 时枚举 $x$ 并贪心扫描，复杂度 $O(n^2)$。

满分算法令 $B=\lceil\sqrt n\rceil$。对 $k\le B$，二分 $x$ 并用贪心检查；对 $x\le B$，直接计算它最多支持的段数 $k$，更新 $f_k$。最后从大到小取后缀最大值，因为能支持 $k$ 段也能支持更少段。

正确性说明

任何划分的公共前缀都对应从位置零开始的若干不重叠前缀出现；反之，把这些出现作为各段起点，并把间隙分配给前一段即可形成划分。最早结束的贪心不会减少后续可选空间，因此得到最大出现次数。平方分治覆盖所有答案：若 $k\le B$ 由第一部分求出，否则 $f_k\le n/k<B+1$，必被第二部分枚举。

复杂度

每组时间复杂度 $O(n\sqrt n\log n)$ 的宽松上界，空间复杂度 $O(n)$。