单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
只需输出以此字母开头的最长的“龙”的长度
5
at
touch
cheat
choose
tact
a
23
// 注释：连成的“龙”为atoucheatactactouchoose
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn = 1000; char str[maxn][maxn]; int mark[maxn] = {0}; char ch,sumch[maxn]; int n; int max1; void show(int len) { max1=len;//曲最长长度 } int check(char ch1[]) {//核对是否符合龙 int len_ch1 = strlen(ch1); int len_sumch = strlen (sumch); int i; for (i=len_sumch-1;i>=0;i--) { if (sumch[i]==ch1[0]) break; } int pos=0; for (int j=i;j<len_sumch;j++) { if (sumch[j]!=ch1[pos++]) return 0; } if (pos==len_ch1) return 0; else return i; } void search() { for (int i=0;i<n;i++) { if (mark[i]<2) {//次数是否出现过两次 int check_pos=check(str[i]); if (check_pos) { int len=strlen(sumch); int pos=0; for (int j=len-check_pos;j<strlen(str[i]);j++) { sumch[len+pos]=str[i][j]; pos++; } if (max1<strlen(sumch))show (strlen(sumch)); mark[i]++; search(); mark[i]--;//回溯 for (int j=len;j<len+pos;j++) sumch[j]=‘\0‘; } } } } int main() { cin >> n; cin.get(); for (int i=0;i<n;i++) { gets(str[i]); } cin >> ch; max1=0; for (int i=0;i<n;i++) { memset(sumch,sizeof(sumch),‘\0‘); memset(mark,sizeof(mark),0); if (str[i][0]==ch) { strcat(sumch,str[i]); mark[i]++; search(); } } cout << max1 << endl; }
原文：http://www.cnblogs.com/xiaoshanshan/p/3550779.html