很明顯，這道題是可以用DFS來做的，我們直接暴力搜索，但是這里有很多點是我們需要注意的。

1.我們如何確定兩個單詞能接上？

比如touch和choose 應該合成為touchoose?

就是這樣兩個單詞，我們讓一個指針指著第一個字符串的末尾，一個指著開頭，然后一個截取后面的子串，一個截取前面的子串，如果相等的話，就拼上

我們要截取的就是s1.substr(cur1)? ?和 s2.substr(0,cur2+1); 然后判斷是否相等，如果相等的話就拼接上

2.我們如何避免 at連接atide這種情況呢？

我們截取子串的時候別截取到全部的就行，我們讓cur1>=1 cur2<s2.size()-1

3.我們不能用全局的字符串，因為那樣回溯的話很難回溯，我們應該把字符串放在參數了

4.我們定義一個cnt數組來給dfs剪紙，因為每個單詞只能用兩遍

5.我們不能直接傳開頭，那樣的話都進不去dfs函數，我們要遍歷一遍所有的字符串，找到開頭一樣的字符串進入dfs

好的，既然我們知道了所有的細節，我們來實現一下代碼吧

#include <iostream>
using namespace std;
const int N = 30;
string s[N];
int n;
int cnt[N];
int ret = 0;
void dfs(string path)
{if(ret<path.size()){ret = path.size();}for(int i = 1;i<=n;i++){if(cnt[i] >= 2) continue;int cur1 = path.size()-1;int cur2 = 0;while(cur1>=1 && cur2 < s[i].size()-1){if(path.substr(cur1)==s[i].substr(0,cur2+1)){cnt[i]++;dfs(path+s[i].substr(cur2+1));cnt[i]--;}cur1--,cur2++;}}
}int main()
{cin >> n;for(int i =1;i<=n;i++){cin >> s[i];}char ch ;cin >> ch;for(int i = 1;i<=n;i++){if(s[i][0] == ch){cnt[i]++;dfs(s[i]);cnt[i]--;}}cout << ret << endl;return 0;
}