Fibnacci string  Problem description The Fibnacci string is as follows:S1=bS2=aSk=Sk-1Sk-2 k>2We are given a string, is there a Fibnacci string? Input The input will consist of a series of string, one string per line, followed by a line containing only the char ‘0’ that signals the end of the input file and need not to be processed.You may assume that the length of each string is no more than 1,000,000. Output For each string you should output the ‘true’ if the string is a Fibnacci string, or ‘false’ if the string is not a Fibnacci string and with one line of output for each line in input.  Sample Input abaababaababaabaababaababa0 Sample Output truetruefalse //友情提示，请注意 a, b my code as followed :#include <stdio.h>#include <stdlib.h>#include <string.h>char gstr[1000010],str[1000010];int  gm[34];void Init(){ int t,i,j; for(i=2,gm[0]=gm[1]=1; gm[i-1]<1000000;i++)  gm[i]=gm[i-1]+gm[i-2]; for(gstr[0]='a',gstr[1]='b',t=2,i=2; i<1000000; t++)  for(j=0; j<gm[t-1] && i<1000000;j++,i++)   gstr[i]=gstr[j];}int myCmp(const int *a,const int *b){ if(*a > *b)  return 1; else if(*a < *b)  return -1; return 0;}int main(){ int  *p,a; char c; Init(); while(1){  scanf("%s",str);  if(!strcmp(str,"0"))   break;  a=strlen(str);  if(a==1){   if(str[0]=='b' || str[0]=='a')    printf("true\n");   else    printf("false\n");   continue;  }  p=bsearch(&a,gm,30,sizeof(int),myCmp);  if(!p){   printf("false\n");   continue;  }  c=gstr[*p];  gstr[*p]='\0';  if(!strcmp(str,gstr))   printf("true\n");  else   printf("false\n");  gstr[*p]=c; } return 0;}

评论