问题描述 

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

输入格式 

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

输出格式 

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

样例输入

　　

　　at

　　touch

　　cheat

　　choose

　　tact

　　a

样例输出

样例说明

　　连成的“龙”为atoucheatactactouchoose

 #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 ;

 }