预处理单词i连接单词j的最小重叠部分,然后dfs即可.
code:
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
int ex[25][25];
string s[25];
int n;
void pre() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int len1 = s[i].length();
int len2 = s[j].length();
for (int k = 1; k <= len1 - 1; ++k) {
int m = 0;
for (; m < len2 - 1 && m < k; ++m) {
if (s[i][len1 - k + m] != s[j][m]) {
break;
}
}
if (m == k && m < len2 - 1) {
ex[i][j] = k;
break;
}
}
}
}
}
int vis[25];
int ans;
void dfs(int i, int len) {
vis[i]++;
// cout<<i<<endl;
int j = 0;
for (j = 0; j < n; ++j) {
if (ex[i][j] && vis[j] < 2) {
dfs(j, len + s[j].length() - ex[i][j]);
vis[j]--;
}
}
if (j == n) ans = max(ans, len);
}
int main() {
// clock_t start,end;
// start=clock();
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
char a;
cin >> a;
pre();
for (int i = 0; i < n; ++i) {
if (s[i][0] == a) {
dfs(i, s[i].length());
vis[i]--;
}
}
cout << ans << endl;
// end=clock();
// cout<<"TIME PASSED:"<<end-start<<endl;
return 0;
}