ABC257G Prefix Concatenation 做题记录

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

1S,T5×1051 \leq |S|,|T| \leq 5\times 10^5

首先有个结论,每次从 TT 末尾删除最长的 SS 的前缀是最优的,因为假设 TT 是由这些蓝色的 SS 的前缀构成的:

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

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

考虑快速求出 TT 中以 TiT_i 结尾的最长的 SS 的前缀,当然可以用后缀数组/后缀自动机来做,但是观察到这个定义和 kmp 数组的定义很像:

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

那么可以令 RRS+TS+TSS 拼上 TT 的字符串,求出 RRkmpikmp_i,然后贪心即可。