Fibonacci 单词
Fibonacci单词定义与Fibonacci数的定义类似: 

FIB(1)=b,FIB(2)=a,FIB(k+2)=FIB(k+1)*FIB(k)(k>=1),*的意思是两个字符串连接,所以FIB3=ab;FIB4=aba;FIB5=abaab; 

现在给出一个长度最多为30的模式串,仅含字母a或b. 

计算第n个Fib单词中含有多少个这样的模式串.模式串在Fib单词中的位置可以重叠. 

Input
该题有多组测试数据,每组测试数据2行,第一行是单词.第二行是n,n<=200. 

Output
模式串出现的次数. 

Sample Input
aba
6

Sample Output
3
高手给个思路吧

---------------------------------------------------------------

修改了下程序

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define INT_LEN 5

typedef unsigned int BIGINT[INT_LEN];

BIGINT C, C1, C2;

typedef unsigned long long longlong;

#define MAX_INT 1000000000

#define MAX_LEN 30
#define MAX_N 200

char pattern[MAX_LEN+1];
char F1[MAX_LEN*3+1],F2[MAX_LEN*3+1],F[MAX_LEN*3+1];
int n;
int pattern_len;

int main(){
    char temp[10];
    int i,j,f1,f2;
    unsigned int c1,c2,x1,x2,c;
    while(fgets(pattern,MAX_LEN+1,stdin)){
    if(!fgets(temp,10,stdin))break;
    n=atoi(temp);
    for(i=0;i<MAX_LEN;i++){
if(pattern[i]=='\0'||isspace(pattern[i]))
    break;
    }
    pattern[i]='\0';/*remove the endline*/
    pattern_len=i;
    f1=1,f2=1;
    F1[0]='b',F1[1]='\0';
    F[0]='a',F[1]='\0';
    strcpy(F2,F);
    for(i=3;;i++){
int f=f1+f2;
strcat(F,F1);
if(f2>=pattern_len||n<=i)break;
f1=f2;f2=f;
strcpy(F1,F2);
strcpy(F2,F);
    }
    if(n==1){
if(strcmp(pattern,"b")==0){
    printf("1\n");
}else{
    printf("0\n");
}
continue;
    }
    j=i;/*F(j)=F,F(j-1)=F2;*/
    /*set c1 to be number of pattern in F(j-1)==F2*\
    \*set c2 to be number of pattern in F(j)==F   */
    for(i=0,c1=0;i<strlen(F2);i++){
if(strncmp(F2+i,pattern,pattern_len)==0){
    c1++;
}
    }
    for(i=0,c2=0;i<strlen(F);i++){
if(strncmp(F+i,pattern,pattern_len)==0){
    c2++;
}
    }
    if(n<=j){
if(n==j-1){
    printf("%d\n",c1);
}else if(n==j){
    printf("%d\n",c2);
}else{
    fprintf(stderr,"Programm error, should never be reached\n");
}
continue;
    }
    /*x1=X(j-1,j), x2=X(j,j+1);*/
    memcpy(F1,F+strlen(F)-pattern_len+1,pattern_len-1);
    memcpy(F1+pattern_len-1,F2,pattern_len-1);
    F1[2*pattern_len-2]='\0';
    for(i=0,x1=0;i<2*pattern_len-2;i++){
if(strncmp(F1+i,pattern,pattern_len)==0){
    x1++;
}
    }
    memcpy(F1,F2+strlen(F2)-pattern_len+1,pattern_len-1);
    memcpy(F1+pattern_len-1,F,pattern_len-1);
    F1[2*pattern_len-2]='\0';
    for(i=0,x2=0;i<2*pattern_len-2;i++){
if(strncmp(F1+i,pattern,pattern_len)==0){
    x2++;
}
    }
    /*now c1=C(j-1),c2=C(j), x1=X(j-1,j), x2=X(j,j+1)*/
    memset(C,0,sizeof(C));
    memset(C1,0,sizeof(C1));
    memset(C2,0,sizeof(C2));
    C1[0]=c1;
    C2[0]=c2;
    for(i=j+1;i<=n;i++){
int k,carry=0;
int extra;
/*C==C1+C2*/
for(k=0;k<INT_LEN;k++){
    longlong r=C1[k];
    r+=C2[k];
    r+=carry;
    C[k]=(unsigned int)r;
    carry=(r>=MAX_INT);
    if(carry)C[k]-=MAX_INT;
}
if((i-j)&1)
    extra=x1;
else
    extra=x2;
for(k=0;k<INT_LEN;k++){
    longlong r=C[k];
    r+=extra;
    C[k]=(unsigned int)r;
    extra=(r>=MAX_INT);
    if(extra)C[k]-=MAX_INT;
    if(extra==0)break;
}
memcpy(C1,C2,sizeof(C));
memcpy(C2,C,sizeof(C));
    }
    for(i=INT_LEN-1;i>=0;i--)if(C[i]!=0)break;
    if(i<0){
printf("0\n");
continue;
    }
    printf("%d",C[i]);
    for(i--;i>=0;i--){
printf("%09u",C[i]);
    }
    printf("\n");
    }
}