【CODEVS 1018】单词接龙

/*
* Copyright © Eliot
* Date: 2016-10-27
* Author: Eliot
* QQ: 1161142536
* Description: 单词接龙
*/

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;

int ans = 0;
map<string, int> Map;
int Judge(string strA, string strB) {
	int nLen = min(strA.length(), strB.length());
	for (int i = 1; i < nLen; i ++) {
		string strLast = strA.substr(strA.length() - i, i);
		string strFirst = strB.substr(0, i);
		
		if (strLast == strFirst) {
			return i;
		}
	}
	return -1;
}

int N = 0;
string strWord[21];
void DFS(string str, int nLen) {
	if (str.length() == 1) {
		for (int i = 1; i <= N; i ++) {
			char ch_1 = strWord[i][0], ch_2 = str[0];
			if (ch_1 == ch_2) {
				Map[strWord[i]] ++;
				if (Map[strWord[i]] > 2) {
					Map[strWord[i]] --;
					continue;
				}
				
				nLen += strWord[i].length(); ans = max(ans, nLen);
				DFS(strWord[i], nLen);
				nLen -= strWord[i].length();
				Map[strWord[i]] --;
			}
		}
	}
	else {
		for (int i = 1; i <= N; i ++) {
			if ((strWord[i].find(str) != string::npos && strWord[i] != str) || (str.find(strWord[i]) != string::npos && strWord[i] != str)) continue;
			int nCoincide = Judge(str, strWord[i]);
			if (nCoincide != -1) {
				Map[strWord[i]] ++;
				if (Map[strWord[i]] > 2) {
					Map[strWord[i]] --;
					continue;
				}
				
				nLen += strWord[i].length() - nCoincide; ans = max(ans, nLen);
				DFS(strWord[i], nLen);
				nLen -= strWord[i].length() - nCoincide;
				Map[strWord[i]] --;
			}
		}
	}
}

string str;
int main () {
	scanf("%d", &N);
	for (int i = 1; i <= N; i ++) {
		cin >> strWord[i];
	}
	cin >> str;
	DFS(str, 0);
	
	cout << ans << endl;
	return 0;
}