前缀连接 题解

思路

设 $L_i$ 表示 $T$ 从位置 $i$ 开始的后缀与 $S$ 的最长公共前缀长度。若当前已经拼出 $T$ 的前 $i$ 个字符，就可以选择任意长度 $1\le d\le L_i$ 的前缀，使已拼出的长度变为 $i+d$。

把每个位置看成顶点，位置 $i$ 向区间 $[i+1,i+L_i]$ 中的所有位置连一条边，题目就是从 $0$ 到 $|T|$ 的最少边数。所有边权都为一，并且每个顶点的出边终点形成连续区间，可以按广度优先搜索的层次只维护当前层最远能到达的位置。

$L_i$ 可以一次性使用 Z 函数求出：对字符串 $S+\texttt{\#}+T$ 求 Z 数组，$T$ 对应位置的 Z 值截断到 $|S|$ 即为 $L_i$。

做法

从左到右扫描 $T$ 的位置，维护当前使用若干个前缀后能覆盖到的层边界，以及从当前层所有可达起点出发能到达的最远位置。

扫描到一个位置时，先用 $i+L_i$ 更新最远位置。到达当前层边界时，必须再使用一个前缀，并把层边界推进到刚得到的最远位置。如果最远位置没有越过当前位置，说明不存在合法前缀可以继续，答案为 $-1$。当层边界达到 $|T|$ 时，使用的层数就是最少前缀数。

Z 函数保证每个 $L_i$ 精确等于从 $i$ 开始可以选择的最长前缀。广度优先搜索的第 $r$ 层包含恰好能用 $r$ 个前缀到达的所有位置；由于每个位置的出边是连续区间，这一层可达位置的并集仍由其最远右端点刻画。逐层扩展最远右端点不会遗漏任何更短方案，因此首次覆盖终点时得到最小值。

复杂度

设 $n=|S|+|T|$。时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。