题目描述 Description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述 Input Description
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述 Output Description
只需输出以此字母开头的最长的“龙”的长度
样例输入 Sample Input
5
at
touch
cheat
choose
tact
a
样例输出 Sample Output
23
数据范围及提示 Data Size & Hint
（连成的“龙”为atoucheatactactouchoose）
还有搜索，dfs。c语言代码，长而且不容易弄懂:-D
AC代码
#include<stdio.h>
#include<string.h>
int max(int x,int y){return x > y? x : y;}
int min(int x,int y){return x < y? x : y;}
char word[80][80];
int flag[80];
int count;
int n;
int check(int m,int n) {
int a = strlen(word[m]);
int b = strlen(word[n]);
int len;
int i;
int j;
int k;
int flag_1;
len = min(a,b);
for(k = 1;k < len;k++) {
flag_1 = 1;
for(i = 0, j = a - k; i < b, j < a; i++, j++) {
if(word[m][j] != word[n][i]) {
flag_1 = 0;
}
}
if(flag_1)
return k;
}
return 0;
}
void dfs(int last,int len) {
int i;
int x;
count = max(count,len);
if(!last) {
for(i = 1;i <= n;i++) {
if(word[i][0] == word[0][0]) {
flag[i]++;
dfs(i,strlen(word[i]));
flag[i]--;
}
}
} else {
for(i = 1; i <= n; i ++) {
x = check(last, i);
if(x && flag[i] < 2) {
flag[i]++;
dfs(i, len + strlen(word[i]) - x);
flag[i]--;
}
}
}
return;
}
int main(void) {
int i;
scanf("%d",&n);
count = 0;
for(i = 1;i <= n;i++) {
scanf("%s",word[i]);
}
scanf("%s",word[0]);
dfs(0,1);
printf("%d\n",count);
return 0;
}