#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int n; vector<string> words; char startChar; int maxLength = 0; // Check if word a is a substring of word b or vice versa bool hasInclusion(const string &a, const string &b) { return b.find(a) != string::npos || a.find(b) != string::npos; } void dfs(const string &currentWord, int usedCount[], int currentLength, int depth) { maxLength = max(maxLength, currentLength); for (int i = 0; i < n; ++i) { const string &nextWord = words[i]; // Check if the next word can be connected to the current word if (currentWord.back() == nextWord[0] && !hasInclusion(currentWord, nextWord)) { if (usedCount[i] < 2) { usedCount[i]++; // The new length is currentLength + nextWord.size() - 1 (overlapping one character) dfs(nextWord, usedCount, currentLength + nextWord.size() - 1, depth + 1); usedCount[i]--; } } } } int main() { cin >> n; words.resize(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } cin >> startChar; int usedCount[n]; fill(usedCount, usedCount + n, 0); for (int i = 0; i < n; ++i) { if (words[i][0] == startChar) { usedCount[i] = 1; dfs(words[i], usedCount, words[i].size(), 1); usedCount[i] = 0; } } cout << maxLength << endl; return 0; }