预处理

先考虑两个字符串之间的拼接代价。

设 $\text{dis}[i][j]$ 表示当前记录以 $s_i$ 结尾时，再让 $s_j$ 出现一次，至少需要额外添加多少个字符。

如果 $s_i$ 的某个后缀等于 $s_j$ 的某个前缀，那么两段可以重叠。令这个最长重叠长度为 $x$，则

$$\text{dis}[i][j]=|s_j|-x。$$

对每个 $s_j$ 建 KMP 的 $\text{nxt}$ 数组，再用每个 $s_i$ 去匹配 $s_j$，匹配结束时保留下来的匹配长度就是最长重叠长度。特别地，当 $i=j$ 时，完全匹配后要退到 border，表示同一个字符串连续出现时只能使用真前后缀重叠。

这一部分复杂度为 $O(n\cdot |S|)$，其中 $|S|$ 为所有字符串总长。

---

30 分做法

在 $n\le 5,m\le 5$ 的数据中，可以直接暴力枚举 $m$ 次分别选择哪个字符串出现。

枚举一个长度为 $m$ 的序列 $p_1,p_2,\ldots,p_m$，它表示依次让 $s_{p_1},s_{p_2},\ldots,s_{p_m}$ 出现。这个序列需要的最短长度为

$$|s_{p_1}|+\sum_{i=2}^{m}\text{dis}[p_{i-1}][p_i]。$$

枚举所有 $n^m$ 种序列，取最小值即可。

---

60 分做法

设

$$\text{dp}[i][j]$$

表示已经安排了 $i$ 次出现，且第 $i$ 次出现的是 $s_j$ 时，当前记录的最小长度。

初始值为

$$\text{dp}[1][j]=|s_j|。$$

转移为

$$\text{dp}[i][j]=\min_k\{\text{dp}[i-1][k]+\text{dis}[k][j]\}。$$

答案为

$$\min_j \text{dp}[m][j]。$$

时间复杂度为 $O(n^2m)$，可以通过 $n\le 50,m\le 1000$ 的数据。

---

100 分做法

上面的 DP 转移形如

$$\text{dp}[i][j]=\min_k\{\text{dp}[i-1][k]+\text{dis}[k][j]\}。$$

这与矩阵乘法很相似，只是把普通乘法换成加法，把求和换成取最小值。这种运算称为 min-plus 矩阵乘法，它满足结合律，因此可以使用快速幂。

构造一个 $(n+1)\times(n+1)$ 的矩阵 $A$，额外加入 $0$ 号点表示空记录：

• $A[0][j]=|s_j|$，表示第一次让 $s_j$ 出现的代价；
• $A[i][j]=\text{dis}[i][j]$，表示在 $s_i$ 后接上 $s_j$ 的代价；
• 其他位置设为 $+\infty$。

在 min-plus 意义下，$A^m[0][j]$ 就表示安排了 $m$ 次出现，最后一次为 $s_j$ 的最小长度。因此答案为

$$\min_{1\le j\le n} A^m[0][j]。$$

矩阵快速幂需要 $O(\log m)$ 次矩阵乘法，每次矩阵乘法复杂度为 $O(n^3)$。

总时间复杂度为

$$O(n\cdot |S|+n^3\log m),$$

空间复杂度为 $O(n^2+|S|)$。

---

关于“至少出现 m 次”

虽然题目要求的是出现次数之和至少为 $m$，但上面的模型只安排了 $m$ 次出现，这是等价的。

一方面，任意一个合法记录 $T$ 中如果已经有至少 $m$ 次出现，可以按出现位置从左到右取出其中前 $m$ 次。由于没有任何 $s_i$ 是另一个 $s_j$ 的子串，相邻两次被取出的出现之间，后一次不可能完全包含前一次；它们之间的新增长度至少是对应的 $\text{dis}$。所以任意合法记录的长度都不会小于 DP 得到的值。

另一方面，DP 或矩阵快速幂给出的拼接方案本身会让选中的 $m$ 个字符串各出现一次，因此一定满足“至少 $m$ 次”的要求。拼接过程中如果额外产生了其他出现，只会让出现次数更多，不影响合法性。

因此求“至少 $m$ 次”的最短长度，可以转化为求安排恰好 $m$ 次指定出现的最短长度。