单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度
NOIp2000提高组第三题
#include<cstdio> #include<cstring> struct doo { char s[21]; int l; int v;//单词出现的次数 }c[21]; int maxn,n; void jl(int x,int l)//待连接单词的序号 l为目前单词接龙的长度 { for(int i=1;i<=n;i++)//寻找可连接单词（待连接单词后连接可连接单词） if(c[i].v<2)//每个单词最多出现两次 for(int j=0;j<c[x].l;j++)//查找待连接单词的每一位 if(c[x].s[j]==c[i].s[0])//找到可衔接的位置 { int k=1; bool t=1; for(int d=j+1;d<c[x].l&&k<c[i].l;k++,d++)//d表示待连接单词下标 k是可连接单词下标 所以在循环条件中需满足它们小于（因为不能包含，所以不能等于）单词长度 if(c[x].s[d]!=c[i].s[k])//从可衔接位置开始判断 若后面的字符并不完全匹配则无法衔接 { t=0; break; } if(t) { c[i].v++; jl(i,l+c[i].l-k);//若可以衔接 找下一个可衔接单词 接龙长度更新 加上当前连接单词的长度 减去重叠部分的长度 c[i].v--; } } if(l>maxn) maxn=l; } int main() { freopen("jl.in","r",stdin); freopen("jl.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",c[i].s); c[i].l=strlen(c[i].s); } scanf("%s",c[0].s); c[0].l=strlen(c[0].s);//直接将开头字母存在0下标 当作第一个单词处理 jl(0,c[0].l); printf("%d",maxn); fclose(stdin); fclose(stdout); return 0; }
