给定仅存在小写英文字母的字符串 。你需要将 分割成 个 的前缀(或着说用 $ S $ 的若干个前缀组成 ),最小化 ,输出最小值。若 不存在输出
-1
。
首先有个结论,每次从 末尾删除最长的 的前缀是最优的,因为假设 是由这些蓝色的 的前缀构成的:

若红色这一段是 的前缀,那它完全可以代替最后那三段 的前缀和第一段 的前缀的后面一段,因为前缀减去末尾的一段依然是前缀:

而若想让组成 的前缀数尽可能少,每个前缀就要尽可能长,所以每次贪心地从 末尾删掉最长的一段 的前缀是最优的。
考虑快速求出 中以 结尾的最长的 的前缀,当然可以用后缀数组/后缀自动机来做,但是观察到这个定义和 kmp 数组的定义很像:
为 的最长的是后缀的前缀长度。
那么可以令 为 即 拼上 的字符串,求出 的 ,然后贪心即可。