问题描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。 输入格式 输入的第一行为一个单独的整数n (n<=)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. 输出格式 只需输出以此字母开头的最长的“龙”的长度 样例输入
at
touch
cheat
choose
tact
a
样例输出 样例说明
连成的“龙”为atoucheatactactouchoose
记:
思路在代码中体现
AC代码:
#include <stdio.h>
#include <string.h>
#define LEN 20
#define MAX 10010 int n; /*单词的个数*/
int max = ; /*最长的"龙"长度*/
char ans[MAX+]; /*最长的"龙"内容*/
char arr[LEN+][MAX+]; /*存储单词*/
int vis[LEN+] = {}; /*每个单词的访问记录*/ void init()
{
int i;
scanf("%d",&n);
for (i = ; i <= n ; i ++)
{
scanf("%s",&arr[i]);
}
return ;
} int check(int x,char tmp[MAX+])
{
int i,j,k;
int len = ,len2 = ; len = strlen(tmp)-; /*原"龙"的长度*/
len2 = strlen(arr[x])-;/*将添加单词的长度*/
for (i = len ; i >= && len2; i --,len2 --)
{
if (tmp[i] == arr[x][])/*找到将添加单词的头*/
{
k = ;
/*检查该单词是否能接"龙"*/
for (j = i+ ; j <= len ; j ++,k ++)
{
if (tmp[j] != arr[x][k])
{
break;/*不能接龙*/
}
} /*该单词能接"龙"*/
if (j>len)
{
return i;/*返回接龙的位置*/
}
}
} return ;
} void dfs(char tmp[MAX+])
{
int i,j;
int len = ;
char add[MAX+]; for (i = ; i < n ; i ++)
{
if (vis[i] < )/*检查次数*/
{
len = check(i,tmp);/*检查能否接龙,0->不能,1->能*/
if (len)
{
/*将单词接到"龙"上*/
for (j = ; j < len ; j ++)
{
add[j] = tmp[j];
}
strcat(add,arr[i]);
vis[i]++;
dfs(add);
vis[i]--;
memset(add,,sizeof(add));
}
}
} len = strlen(tmp);
if (len > max)
{
max = len; /*更新最长的"龙"长度*/
//strcpy(ans,tmp);/*更新最长的"龙"内容*/
}
return ;
} int main(void)
{
int i;
init();
for (i = ; i < n ; i ++)
{
/*以最后一个单词为头的单词*/
if (arr[i][] == arr[n][])
{
vis[i]++;
dfs(arr[i]);
vis[i]--;
}
}
printf("%d",max);
return ;
}