预处理两个单词接龙的最长len dfs暴搜即可。需要恢复现场,原因是要求最长len
// author:leimingze
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define _ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define LL long long
#define ULL unsigned unsigned
#define PII pair<int,int>
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define eps 1e-8
const double PI = acos(-1.0);
const int dx4[4] = { 0,-1,0,1 };
const int dy4[4] = { -1,0,1,0 };
//#pragma warning(disable:4786)//使命名长度不受限制
//#pragma comment(linker, "/STACK:102400000,102400000")//手工开栈
int qmi(int a, int k, int p) { int res = 1 % p; while (k) { if (k & 1)res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; }return res; }
template <typename T> void inline read(T& x)
{
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
//不开long long 见祖宗,递归剪枝
const int N = 21;
int n;
string word[N];
char g[N][N];
int st[N];
int res;
void dfs(string state, int idx)
{
res = max(res, (int)state.size());
st[idx]++;
for (int i = 0; i < n; i++)
if (g[idx][i] && st[i] < 2)
dfs(state + word[i].substr(g[idx][i]), i);
st[idx]--;
}
void solve()
{
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) == 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 << res << endl;
}
int main()
{
solve();
return 0;
}