#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int MAX_N = 20; vector<string> words; // 存储所有单词 int overlap[MAX_N][MAX_N]; // overlap[i][j]表示单词i后接单词j的最大重合长度 int used[MAX_N]; // 记录每个单词的使用次数（0/1/2） int max_len; // 最长龙的长度 int n; // 单词数量 // 计算两个单词a和b的最大重合长度（a的后缀和b的前缀） int calc_overlap(const string& a, const string& b) { int max_over = 0; // 重合长度最多为min(a.length(), b.length())-1（避免包含） int max_possible = min(a.length(), b.length()) - 1; for (int len = 1; len <= max_possible; ++len) { // 取a的最后len个字符，b的前len个字符 string a_suffix = a.substr(a.length() - len, len); string b_prefix = b.substr(0, len); if (a_suffix == b_prefix) { max_over = len; } } return max_over; } // DFS函数：last是上一个使用的单词索引，current_len是当前龙的长度 void dfs(int last, int current_len) { // 更新最大长度 if (current_len > max_len) { max_len = current_len; } // 尝试拼接所有可用的单词 for (int i = 0; i < n; ++i) { // 单词i使用次数不足2次，且与上一个单词有有效重合 if (used[i] < 2 && overlap[last][i] > 0) { used[i]++; // 新长度 = 当前长度 + 单词i长度 - 重合长度 dfs(i, current_len + words[i].length() - overlap[last][i]); used[i]--; // 回溯 } } } int main() { cin >> n; words.resize(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } char start_char; cin >> start_char; // 预处理所有单词对的重合长度 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { overlap[i][j] = calc_overlap(words[i], words[j]); } } // 初始化 max_len = 0; fill(used, used + n, 0); // 遍历所有以起始字母开头的单词，作为接龙起点 for (int i = 0; i < n; ++i) { if (words[i][0] == start_char) { used[i] = 1; dfs(i, words[i].length()); used[i] = 0; // 回溯 } } cout << max_len << endl; return 0; }