我们经常看到火车都是一串的，它们由一节节车厢连成一列火车组。每节车厢连接是有规则的，规则如下：每种车厢都有它唯一标识的一个单词，现在给定一个单词开头的字母，求出以这个字母开头的最长的火车组（每种车厢最多在火车组中出现两次），在两个单词相连时，其重合部分算作一部分，例如money和neymar，如果接成一列火车组则变为moneymar，另外相邻的两部分不能存在包含关系，例如break和breakfast 不能相连。 输入
输入的第一行为一个正整数n (n<=20)表示车厢种数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示火车组开头的字母。假定以此字母开头的火车组一定存在。 输出
只需输出以此字母开头的最长的火车组的标识符长度。 输入范例
6 many youth this system main navy m 输出范例
38 Hint 连成的火车组标识符为manyouthisystemainavyouthisystemainavy DFS然后加上字符串的处理就行了。注意是每个单词用两次。加个计数的解决了。 #include #define max(a,b) a>b?a:b #define min(a,b) a using namespace std ; typedef long long ll; typedef unsigned long long ull; string s[21]; int k[21]; char b; int Max,t; void dfs(string ans){ Max = max(Max,ans.length()); if(!ans.length()){ for(int i = 1 ; i <= t ; i++){ if(s[i][0] == b){ k[i]++; dfs(ans+s[i]); k[i]--; } } } else{ for(int i = 1 ; i <= t ; i++){ if(k[i]==2) continue; int j = 1 ; while(ans[ans.length()-j]!=s[i][0]){ j++; if(ans.length()-j <= 0){ j--; break; } if(j >= s[i].length()){ j--; break; } } if(s[i].substr(0,j) == ans.substr(ans.length()-j)){ k[i]++; dfs(ans.substr(0,ans.length()-j)+s[i]); k[i]--; } } } } int main(){ while(cin>>t){ for(int i = 1 ; i <= t ; i++) cin>>s[i]; memset(k,0,sizeof(k)); string ans=""; cin>>b; Max=0; dfs(ans); cout<return 0; }