本地笔记整理重发，原文写于 2019/8/28，2019/12/8 上传
分析
首先使用哈希计算字符串两两之间的 overlap，这个的时间复杂度不是特别显然： \[ \sum_{i=1}^n\sum_{j=1}^n\min\{a_i,a_j\} \] 其中 \(a_i, a_j\) 分别是第 \(i\) 个和第 \(j\) 个字符串的长度。假设 \(a_i\) 从小到大排了序，那么就变为： \[ \sum_{i=1}^n \left[\sum_{j=1}^ia_j+(n-i)a_i\right] \] 这样每一个 \(a_i\) 都会被计算 \(n-i+1+n-i=2n-2i+1\) 次，则时间复杂度为： \[ \begin{aligned} \sum_{i=1}^n (2n-2i+1)a_i \end{aligned} \] 显然这个时候越前面的 \(a_i\) 越大越好，但是 \(a_i\) 是递增的，所以极限情况是各 \(a_i\) 相等取最大值，时间复杂度就是 \(O\left(n\sum_{i=1}^na_i\right)\)。
然后 Floyd 矩阵乘法即可。
双哈希大法好
卡常 Nice
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MOD1 = 998244353, MOD2 = 1e9 + 7;
const int EPS = 26;
const int N = 210;
const int S = 100010;
typedef long long ll;
typedef pair<int, int> hsh;
int n, m;
vector<hsh> h[N];
hsh p[S];
inline hsh operator +(const hsh &a, const hsh &b) {
hsh ret = make_pair(a.first + b.first, a.second + b.second);
if (ret.first >= MOD1) ret.first -= MOD1;
if (ret.second >= MOD2) ret.second -= MOD2;
return ret;
}
inline hsh operator -(const hsh &a, const hsh &b) {
hsh ret = make_pair(a.first - b.first, a.second - b.second);
if (ret.first < 0) ret.first += MOD1;
if (ret.second < 0) ret.second += MOD2;
return ret;
}
inline hsh operator +(const hsh &a, char b) {
int c = b - 'a';
return make_pair(((ll)a.first * EPS + c) % MOD1,
((ll)a.second * EPS + c) % MOD2);
}
inline hsh operator *(const hsh &a, const hsh &b) {
return make_pair((ll)a.first * b.first % MOD1,
(ll)a.second * b.second % MOD2);
}
inline hsh cut(int i, int l, int r) {
return h[i][r] - h[i][l] * p[r - l];
}
inline int intersect(int a, int b) {
int la = h[a].size() - 1, lb = h[b].size() - 1;
int lim = a == b ? la - 1 : min(la, lb);
int ret = 0;
for (int i = 1; i <= lim; i++)
if (cut(a, la - i, la) == cut(b, 0, i)) ret = i;
return ret;
}
struct floyd {
ll d[N][N];
floyd() { memset(d, 0x3f, sizeof d); }
ll *operator [](int x) { return d[x]; }
const ll *operator [](int x) const { return d[x]; }
floyd operator *(const floyd &b) const {
floyd ret;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ret[i][j] = min(ret[i][j], d[i][k] + b[k][j]);
return ret;
}
} f;
int main() {
scanf("%d%d", &n, &m);
int maxlen = 0;
for (int i = 1; i <= n; i++) {
static char tmp[S]; scanf("%s", tmp + 1);
int len = strlen(tmp + 1);
maxlen = max(maxlen, len);
h[i].push_back(make_pair(0, 0));
for (int j = 1; j <= len; j++)
h[i].push_back(h[i].back() + tmp[j]);
}
p[0] = make_pair(1, 1);
for (int i = 1; i <= maxlen; i++) p[i] = p[i - 1] * make_pair(EPS, EPS);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = h[j].size() - 1 - intersect(i, j);
floyd ans; for (int i = 1; i <= n; i++) ans[i][i] = h[i].size() - 1;
int y = m - 1;
for (; y; y >>= 1) {
if (y & 1) ans = ans * f;
f = f * f;
}
ll mn = 1ll << 60;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) mn = min(mn, ans[i][j]);
printf("%lld\n", mn);
return 0;
}