单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
只需输出以此字母开头的最长的“龙”的长度
5 at touch cheat choose tact a
23 （连成的“龙”为atoucheatactactouchoose）
NOIP2000提高组第三题 NOIP2000普及组第四题
总的来说，这道题虽说不难，却很“坑”。
这是一道深搜题，我们先要确定两单词重合部分的“头”，可以采取将后一个字符串的第一个字符与前一个字符串的第i个字符(i=len-1;i>0;i–)需要注意是逆序查找(之后会解释)。因此可以得到前一个串的重合部分的开始位置，同时也要向后遍历一遍核对每一个字母都对应相同吗，我们就可以完全确定两个字符串是否能够相连，再将现在所连的总单词长度求出，进入下一轮搜索即可。
对于前三个测试数据，关键是在理解在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。这句话的含义，实际上，这种包含也有特殊情况例如样例#1: 1 envelope e 对于这组数据，我们可以将envelope与envelope相连的情况的龙看作envelope，这是一种包含关系，是不可取的。但同时我们也可以将龙看作是e，是可取的。连接后的单词为envelopenvelope长度为15.那么，我们到底是以哪一种思考方向面对这个数据呢？题目的要求是求出以这个字母开头的最长的“龙”因此我们因该与最长的那一串即15为结果。从这三组数据就可以解释前面找两单词重合部分的“头”的逆序查找的原因了。 对于第四个测试数据，也是一个非常“经典”的坑,让我们看看这组数据吧： 样例#4: 8 no new name never national necessary ever me n 接来接去，有没有发现namever就是所有单词中唯一能够接上的一组。所以答案就是7了吗？然而事实并不是那么简单，再当我们仔细数数每个单词的时候，我们会发现necessary这个单词本来就比namever长！因此在写代码时必须要注意第一次找以字母n开头的单词时，也要将它与最大值比较。 数据5,6，没有坑点，故一笔略过。
接下来就放代码了
#include<bits/stdc++.h> using namespace std; int n,j,ans,b[25],maxx,k; string a[25],c[25]; char h,head; void dfs(int m) { for(int i=1;i<=n;i++) { if(b[i]<2) { int q,p=c[m-1].length(),flag=1,fk=0; for(int j=p;j>0;j--) if(c[m-1][j]==a[i][0]){q=j;fk=1;break;} if(fk) { for(int k=q+1;k<=p-1;k++) if(c[m-1][k]!=a[i][k-q]){flag=0;break;} if(flag&&p-q!=a[i].length()) { ans+=(a[i].length()-(p-q)); c[m]=a[i]; maxx=max(maxx,ans); b[i]++; dfs(m+1); ans-=(a[i].length()-(p-q)); b[i]--; } } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)cin>>a[i]; getchar(); scanf("%c",&head); for(int i=1;i<=n;i++) { ans=0; if(head==a[i][0]) { ans+=a[i].length(); maxx=max(maxx,ans); c[1]=a[i]; b[i]++; dfs(2); b[i]--; } } printf("%d",maxx); }