单词接龙（字符串处理+dfs）搜索与回溯

【题目描述】
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
【输入】
输入的第一行为一个单独的整数n(n≤20)表示单词数，以下n行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
【输出】
只需输出以此字母开头的最长的“龙”的长度。
【输入样例】
5
at
touch
cheat
choose
tact
a
【输出样例】
23
题目分析：
这个题难不是难在搜索函数的编写，而是字符串处理那个函数的编写，我看了好久才看懂，其实遇到看不懂的就应该拿草纸手动模拟一遍，能展现的比较直观。等写熟了就自然而然能写出这种函数了。
思路
从所给的龙头字母开始搜索，设置一个数组记录每个单词的使用次数，不得超过两次，还要确保前后两个单词能够连接。跟常规dfs没什么区别。
下面是字符串处理函数：

int lian(string s1,string s2) { int minx=9999999; for(int k=1; k<=s1.length(); k++) { int i=s1.length()-1； int j=k-1; int flag=0; while(i>=0&&j>=0) { if(s1[i]==s2[j]) { j--; i--; } else { flag=1; break; } } if(!flag) { minx=min(k,minx); } } if(minx>999) return 0; else return minx; }

【单词接龙（字符串处理+dfs）】解释：
i指针永远指向s1串的最后一个字母，而j指针则一开始指向s2串的第一个字母。
比如寻找touch和cheat的重叠部分‘ch’。一开始i=4指向s1的h字母，而j则指向s2的c字母，不相等，则跳出此次循环，之后执行了k++，这时j指向的是s2的第二个字母h这时i和j所指向的字母相等，则从此时开始分别执行i–与j–搜索h前的字母是否相等，相等的话接着向前搜索或者到达了s2的第一个字母while循环结束，储存此时的k，k即为重叠串的长度。
代码：

#include #include using namespace std; string word[101]; int use[101],n; int sum=0,len=0; int chong[101][101]; void dfs(int); //搜索函数 int lian(string,string); //计算两个字符串重叠部分的长度，能连接则返回长度，不能连接则返回0。 int main() { cin>>n; for(int i=1; i<=n; i++) cin>>word[i]; char s; cin>>s; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) chong[i][j]=lian(word[i],word[j]); //遍历整个字符串数组 for(int i=1; i<=n; i++) { if(word[i][0]==s) { use[i]++; len+=word[i].length(); if(len>sum) sum=len; dfs(i); len-=word[i].length(); use[i]--; } } cout<; return 0; } void dfs(int i) { for(int j=1; j<=n; j++) { if(chong[i][j]&&use[j]<2)//使用次数不能大于2并且要保证可以连接 { use[j]++; len+=word[j].length()-chong[i][j]; if(len>sum) sum=len; dfs(j); use[j]--; len-=word[j].length()-chong[i][j]; } } } int lian(string s1,string s2) { int minx=9999999; for(int k=1; k<=s1.length(); k++) { int i=s1.length()-1; int j=k-1; int flag=0; while(i>=0&&j>=0) { if(s1[i]==s2[j]) { j--; i--; } else { flag=1; break; } } if(!flag) { minx=min(k,minx); } } if(minx>999) return 0; else return minx; }