分析

• 前一个单词的后缀和后一个单词的前缀相等即可将两个单词拼接，并且拼接部分的长度要大于1，同时小于两个单词中任意一个单词的长度。

• 分为两步：

（1）预处理出一个二维数组g，g[i][j]=k表示第j个单词可以接到第i个单词前面，且最小的重合部分长度为k。

（2）暴搜所有方案。

#include <iostream>

using namespace std;

const int N = 21;

int n;
string word[N];
int g[N][N];  // 有向有权图
int used[N];  // 记录单词使用了几次
int ans;

// last表示当前考察的单词的编号
void dfs(string dragon, int last) {

    ans = max((int)dragon.size(), ans);

    used[last]++;
    for (int i = 0; i < n; i++)
        if (g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);
    used[last]--;
}

int main() {

    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;

    // 建图
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k++)
                if (a.substr(a.size() - k, k) == b.substr(0, k)) {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i++)
        if (word[i][0] == start)
            dfs(word[i], i);

    cout << ans << endl;

    return 0;
}