题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

在连接时，要保证两个单词之间使用最短的重合部分进行接龙，且两个单词相互之间不能有包含的情况，特殊情况是两个相同的单词之间可以互相连接，使用最短的重合部分。

输入格式

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度

样例

样例输入

复制5
at
touch
cheat
choose
tact
a

样例输出

复制23

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
int n,ans;
char m;
int b[25];
string a[25];
int check(string s,string t){
	int v=0;
	for(int i=0;i<s.size();i++){
		int k=i,j;
		for(j=0;k<s.size()&&j<t.size();j++,k++){
			if(s[k]!=t[j])break;
		}
		if(k==s.size())v=k-i;
	}
	return v;
}
void dfs(int l,int x){
	ans=max(ans,l);
	for(int i=1;i<=n;i++){
		if(b[i]<2){
		    int y=check(a[x],a[i]);
			if(y==0)continue;
			b[i]++;
			dfs(l+a[i].size()-y,i);
			b[i]--;
		}
	}
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
   	    cin>>a[i]; 
    }
    cin>>m;
    for(int i=1;i<=n;i++){
    	if(a[i][0]==m){
    		b[i]++;
    		dfs(a[i].size(),i);
    		b[i]--;
		}
	}
	cout<<ans;
}