单词接龙  Problem description 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“ 龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。  Input 输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。 你可以假定以此字母开头的“龙”一定存在。  Output 只需输出以此字母开头的最长的“龙”的长度。  Sample Input 5attouchcheatchoosetacta Sample Output 23 Problem Source NOIP2000  // 开始题意理解错了，提交几次都不成功，后来仔细想了想，呵终于AC了// 下面是代码// 主要用到了栈，其次就是字符串的灵活处理。 #include <stdio.h>#include <stdlib.h>#include <string.h> #define MAX_WORD_LENGTH 20#define MAX_WORD 20#define WORD_USE_MAX 2#define TRUE 1#define FALSE 0#define FAILED 1#define SUCCESS !FAILED typedef struct stackk{ int  findIndex; int  wordIndex; int  addLength;}STACK; STACK stk[MAX_WORD * 2 + 2];char  word[MAX_WORD][MAX_WORD_LENGTH];char  wordUseStatus[MAX_WORD];char  dragon[MAX_WORD * MAX_WORD_LENGTH]; int initDragon(char head,int *index,int nWord,int *length){ int i = *index;  for(; i < nWord; i ++){  if(word[i][0] == head){   *index = i + 1;   wordUseStatus[i] = 1;   *length = strlen(word[i]);   stk[0].addLength = *length;   stk[0].findIndex = 0;   stk[0].wordIndex = i;   strcpy(dragon,word[i]);   return SUCCESS;  } } return FAILED;} int pushDragonWord(int stkIndex,int nWord,int *length){ int  i,j,add; char *pDragonEnd,*pWord,*pStart,*pEnd;  i = stk[stkIndex].findIndex; pDragonEnd = dragon + strlen(dragon) - 1; for(i; i < nWord; i++){  if(wordUseStatus[i] >= WORD_USE_MAX)   continue;  if(strlen(dragon) > strlen(word[i]))   pEnd = dragon+(strlen(dragon)-strlen(word[i]));  else   pEnd = dragon;  pStart=pDragonEnd;  for(j=0,pWord=&word[i][0]; pStart!=pEnd && *pWord && *pStart;){   if(*pWord != *pStart){    pStart = pDragonEnd - (++j);    pWord = &word[i][0];   }   else{    pWord++;    pStart++;   }  }  if(*pStart == '\0'){    pStart = pDragonEnd - j;    add = strlen(word[i]) - strlen(pStart);    *length = *length + add;    stk[stkIndex].findIndex = i + 1;    stk[stkIndex+1].addLength = add;    stk[stkIndex+1].findIndex = 0;    stk[stkIndex+1].wordIndex = i;    wordUseStatus[i] ++;    strcpy(pStart,word[i]);    return SUCCESS;  } } return FAILED;} void popDragonWord(int stkIndex,int *length){ stk[stkIndex-1].findIndex = stk[stkIndex].wordIndex + 1; *(dragon + strlen(dragon) - stk[stkIndex].addLength) = '\0'; *length = *length - stk[stkIndex].addLength; wordUseStatus[ stk[stkIndex].wordIndex ] --;} int main(){ int  i,nWord,stkIndex,startIndex; int  tempLength,maxLength; char dragonHead;  scanf("%d",&nWord); for(i = 0; i < nWord; i ++)  scanf("%s",word[i]); getchar(); scanf("%c",&dragonHead); memset(wordUseStatus,0,MAX_WORD); for(maxLength = tempLength = startIndex = 0;;){  if(initDragon(dragonHead,&startIndex,nWord,&tempLength) == FAILED)   break;    else    stkIndex = 0;  while(TRUE){   if(pushDragonWord(stkIndex,nWord,&tempLength) != FAILED)    stkIndex ++;   else if(stkIndex > 0){    maxLength = (tempLength > maxLength ? tempLength : maxLength);    popDragonWord(stkIndex,&tempLength);    stkIndex --;   }   else    break;  }  maxLength=(tempLength>maxLength ? tempLength : maxLength); } printf("%d\n",maxLength); return 0;}

评论