KMP暴力求出next数组后
实际上是一个最短路问题，floyed搞一搞 然而会TLE 矩阵优化一下即可（倍增floyed）# include# include # include # include # include # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}int n, m, nxt[210][100010], len[210];char s[210][100010];struct Matrix{ ll a[210][210]; IL void Clear(){ Fill(a, 63); } IL ll* operator [](RG int x){ return a[x]; } IL Matrix operator *(RG Matrix &B){ RG Matrix C; C.Clear(); for(RG int i = 0; i <= n; i++) for(RG int j = 0; j <= n; j++) for(RG int k = 0; k <= n; k++) C[i][k] = min(C[i][k], a[i][j] + B[j][k]); return C; }} ans, edge;int main(RG int argc, RG char* argv[]){ edge.Clear(); ans.Clear(); n = Read(); m = Read(); for(RG int i = 1; i <= n; i++) scanf(" %s", s[i] + 1), len[i] = strlen(s[i] + 1); for(RG int k = 1; k <= n; k++) for(RG int i = 2, j = 0; i <= len[k]; i++){ while(j && s[k][j + 1] != s[k][i]) j = nxt[k][j]; if(s[k][j + 1] == s[k][i]) j++; nxt[k][i] = j; } for(RG int x = 1; x <= n; x++){ edge[0][x] = len[x]; for(RG int y = 1; y <= n; y++) for(RG int i = 2, j = 0; i <= len[x]; i++){ while(j && s[y][j + 1] != s[x][i]) j = nxt[y][j]; if(s[y][j + 1] == s[x][i]) j++; if(i == len[x]) edge[x][y] = len[y] - j; } } for(RG int i = 0; i <= n; i++) ans[i][i] = 0; for(; m; m >>= 1, edge = edge * edge) if(m & 1) ans = ans * edge; RG ll min_len = 1e18; for(RG int i = 1; i <= n; i++) min_len = min(ans[0][i], min_len); printf("%lld\n", min_len); return 0;}