题解

思路

把每个字符串在文本中的每次出现看成一个闭左开右区间。问题转化为：从这些区间中选出最少的若干个，使它们的并集覆盖整个文本。

设当前已经连续覆盖了文本的前缀，下一次必须选择一个左端点不超过当前边界、且右端点超过当前边界的区间。为了使操作数最少，应当选择其中右端点最远的区间。

做法

先枚举每个字符串的所有出现位置。令当前已覆盖前缀的右边界为零。反复考察所有左端点不超过当前边界的出现，选择右端点最大的一个，把边界推进到该右端点，并记录字符串编号和开始位置。

如果某一步找不到能越过当前边界的出现，则当前字符无法被染色，答案为 $-1$。当边界到达文本末尾时，记录的出现就是一个最优方案。

正确性可以用交换论证说明。任意可行最优方案中，覆盖当前第一个未染色位置的操作，其左端点不超过当前边界。把该操作替换为所有候选中右端点最远的操作，不会减少已经覆盖的范围，也不会增加后续所需操作数。因此每一步的贪心选择都可以出现在某个最优方案中，递推即可得到全局最优解。

复杂度

设 $L=|t|$。直接枚举出现并在每一步扫描候选，时间复杂度为 $O(nL^2)$，空间复杂度为 $O(nL)$；在本题范围内满足限制。