ABC257G Prefix Concatenation 做题记录

给定仅存在小写英文字母的字符串 $S, T$。你需要将 $T$ 分割成 $k$ 个 $S$ 的前缀（或着说用 $ S $ 的若干个前缀组成 $T$），最小化 $k$，输出最小值。若 $k$ 不存在输出 -1。

$1 \leq |S|,|T| \leq 5\times 10^5$

首先有个结论，每次从 $T$ 末尾删除最长的 $S$ 的前缀是最优的，因为假设 $T$ 是由这些蓝色的 $S$ 的前缀构成的：

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

而若想让组成 $T$ 的前缀数尽可能少，每个前缀就要尽可能长，所以每次贪心地从 $T$ 末尾删掉最长的一段 $S$ 的前缀是最优的。

考虑快速求出 $T$ 中以 $T_i$ 结尾的最长的 $S$ 的前缀，当然可以用后缀数组/后缀自动机来做，但是观察到这个定义和 kmp 数组的定义很像：

$kmp_i$ 为 $s_{[1,i]}$ 的最长的是后缀的前缀长度。

那么可以令 $R$ 为 $S+T$ 即 $S$ 拼上 $T$ 的字符串，求出 $R$ 的 $kmp_i$，然后贪心即可。