题目描述

描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入输出格式

输入格式：

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式：

只需输出以此字母开头的最长的“龙”的长度

输入输出样例

输入样例#1：

5
at
touch
cheat
choose
tact
a

输出样例#1：

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);
}