使用BFS去搜索每一个可以添加的单词，然后将所有的可能性搜索一遍之后取最大的。
关键点：如何进行字符串的匹配：将s1从后向前遍历，如果与s2的第一个匹配上了就接着向前走，如果知道s1的末尾都通过的话就证明可以匹配上。不用真的拼接上去，只需要记录拼接后的长度就行。
拼接后的长度：两个字符串的长度之和-重复的长度。 
#include <bits/stdc++.h>


using namespace std;
const int maxn = 20+4;
string s[maxn];
int begin_pos[maxn];
int cnt = 0;
map<int, int> mp;
char beginc;
int n;
int temp = -1;
//判断s1的末尾和s2的首部是否有重叠之处，返回重叠的长度
int check(string s1, string s2) {
    bool flag = true;
    for (int i=s1.length()-1; i>=0; i--) {
        if (s1[i]==s2[0]) {
            int pos = 0;
            for (int j=i;j<s1.length();j++) {
                if (s1[j]!=s2[pos++]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return pos;
            }
        }
    }
    return 0;
}

int DFS(string last, int num) {
    for (int i=0;i<n;i++) {
        if (mp[i]==2) continue;
        int repeat_len = check(last, s[i]);
        if (repeat_len) {
            mp[i]++;
            DFS(last+s[i], num+s[i].length()-repeat_len);
            mp[i]--;
        }
    }
    return temp = max(temp, num);
}

int main() {
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>s[i];
    }
    cin>>beginc;
    for (int i=0;i<n;i++) {
        if (s[i][0]==beginc) {
            begin_pos[cnt++] = i;
        }
    }
    int ans = 0;
    //以不同的单词开头去进行DFS搜索
    for (int i=0;i<cnt;i++) {
        mp.clear();
        mp[begin_pos[i]] = 1;
        ans = max(ans, DFS(s[begin_pos[i]], s[begin_pos[i]].length()));
    }
    cout<<ans;
    return 0;
}