单词接龙 
Problem description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“

龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为

beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

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

你可以假定以此字母开头的“龙”一定存在。

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

 
Sample Input
5
at
touch
cheat
choose
tact
a
 
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;
}

评论