题目描述： 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。 输入格式： 输入的第一行为一个单独的整数n (n≤20)表示单词数，以下nnn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. 输出格式： 只需输出以此字母开头的最长的“龙”的长度。 样例： 输入： 5 at touch cheat choose tact a 输出： 23 思路：在看了诸多大神的题解后，我终于明白了（本人蒟蒻），首先用string存储 单词，string可以直接拼接字符，然后使用dfs进行筛选标记，筛选满足要求的单词。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; string str[25]; string str1; int vis[100]; int n; int sum; int ans; void add(string &a,string str,int k) { int len = str.length(); for(int i = k; i < len; i ++ ) { a += str[i]; //string类可以直接拼接字符; } } int chek(string a,string str,int k) { int len = a.length(); for(int i = 0; i < k; i ++ ) { if(a[len + i - k] != str[i]) // k从1开始，因为字符串a的长度为len，但是数组是0 ~ len - 1,str的下标也是从0 ~ k，所以这个判断相当于用a最后一个字符，与str的第一个字符进行对比，判断是否相等，并循环依次对比。 return 0; } return 1; //字符相等返回1； } void dfs(string a) { int len = a.length(); ans = max(len,ans); //存储字符串长度； for(int i = 1; i <= n; i ++ ) { if(vis[i] >= 2) continue; //用过两次的单词不能再用； int lent = str[i].length(); for(int j = 1; j <= lent; j ++ ) { if(chek(a,str[i],j)) { string temp = a; add(temp,str[i],j); //单词的第j个字符之前的所有字符都与字符串尾部字符匹配，把单词第j个字符之后的不同字符加入字符串。 if(temp == a) continue; //加字符后字符串没变，说明存在包含关系，跳过，重新查找。 vis[i] ++ ; // 标记此单词； dfs(temp); vis[i] -- ; } } } } int main() { cin >> n; memset(vis,0,sizeof(vis)); for(int i = 1; i <= n; i ++ ) cin >> str[i]; //存储单词 cin >> str1; //存储”龙头” ans = 0; dfs(str1); cout << ans << endl; return 0; }