题意

给出$n$个字符串，求他们相连的最小长度，如果首尾字母相同则可以共用相同部分，比如两个串$ABCDEF$和$DEFGHI$，他们相连为$ABCDEFGHI$，最小长度为$9$，中间的$DEF$部分共用了。

思路

由于数据量较小，首先对每两个字符串$a，b$用扩展$KMP$求出$a$连在$b$之后可以共用的长度，用数组$B[i][j]$表示第$j$个字符串连接在第$i$个字符串后面能共用的最大长度。 1.在扩展$KMP$函数中求子串$a$和母串$b$的公共前缀数组$ret[i]$（子串、母串、公共前缀数组，为了理解方便，我就这么叫了），如果此时$ret[i]$与$strlen(b)-i$的值相等，说明$b$串剩下的部分和$a$串的前$strlen(b)-i$个字符完全相等，则这个值就是我们需要的值，因为$i$是从小到大的，所以如果找到符合的$strlen(b)-i$值，最先出现的这个值一定是最大的，即可返回，如果最后没有找到符合的值，说明没有$b$串的后缀和$a$串的前缀相等，则返回$0$。 2.找完了数组$B$中所有值之后，考虑到一个字符串最多只能连在一个字符串的后面，并且身后也最多只能连接一个字符串，而且此题数据较小，可以用$dfs$来枚举，枚举每个串当首串的情况（即它不连在其他串之后），然后$dfs$枚举每个串连在它身后的情况，找出这之中的最小值，就是我们需要的答案。

标程

#include <cstring>
#include <cstdio>
#include <algorithm>

#define PI acos(-1.0)
#define MAXN 10100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

char a[15][25];
int next[MAXN], ret[MAXN];
int b[15][15], vis[15];
int ans, n;

int ExtendKMP(char a[], char b[]) {
    int i, j, k;
    int M = strlen(a);
    int N = strlen(b);
    
    for (j = 0; 1 + j < M && a[j] == a[1 + j]; j++);
    next[1] = j;
    k = 1;
    for (i = 2; i < M; i++) {
        int Len = k + next[k], L = next[i - k];
        if (L < Len - i) {
            next[i] = L;
        } else {
            for (j = (Len - i > 0) ? (Len - i) : 0; i + j < M && a[j] == a[i + j]; j++);
            next[i] = j;
            k = i;
        }
    }
    
    for (j = 0; j < N && j < M && a[j] == b[j]; j++);
    if (j == N) return N;
    ret[0] = j;
    k = 0;
    for (i = 1; i < N; i++) {
        int Len = k + ret[k], L = next[i - k];
        if (L < Len - i) {
            ret[i] = L;
        } else {
            for (j = (Len - i > 0) ? (Len - i) : 0; j < M && i + j < N && a[j] == b[i + j]; j++);
            ret[i] = j;
            k = i;
        }
        if (ret[i] == N - i) return ret[i];
    }
    return 0;
}

void dfs(int x, int tot, int len) {
    int i;
    if (tot == n) {
        if (ans > len) ans = len;
        return;
    }
    if (len > ans) return;
    for (i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            dfs(i, tot + 1, len + strlen(a[i]) - b[i][x]);
            vis[i] = 0;
        }
    }
}

int main() {
    int t, i, j;
    scanf("%d", &t);
    while (t--) {
        memset(b, 0, sizeof(b));
        memset(vis, 0, sizeof(vis));
        ans = INF;
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            scanf("%s", a[i]);
        }
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (i == j) continue;
                b[j][i] = ExtendKMP(a[i], a[j]);
            }
        }
        for (i = 0; i < n; i++) {
            vis[i] = 1;
            dfs(i, 1, strlen(a[i]));
            vis[i] = 0;
        }
        printf("%d\n", ans);
    }
    return 0;
}