Revenge of Fibonacci

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 204800/204800 K (Java/Others)
Total Submission(s): 2895    Accepted Submission(s): 734

Problem Description
The well-known Fibonacci sequence is defined as following:


  Here we regard n as the index of the Fibonacci number F(n).
  This sequence has been studied since the publication of Fibonacci's book Liber Abaci. So far, many properties of this sequence have been introduced.
  You had been interested in this sequence, while after reading lots of papers about it. You think there’s no need to research in it anymore because of the lack of its unrevealed properties. Yesterday, you decided to study some other sequences like Lucas sequence instead.
  Fibonacci came into your dream last night. “Stupid human beings. Lots of important properties of Fibonacci sequence have not been studied by anyone, for example, from the Fibonacci number 347746739…”
  You woke up and couldn’t remember the whole number except the first few digits Fibonacci told you. You decided to write a program to find this number out in order to continue your research on Fibonacci sequence.
 

Input
  There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases (T<=50000).
  For each test case, there is a single line containing one non-empty string made up of at most 40 digits. And there won’t be any unnecessary leading zeroes.
 

Output
  For each test case, output the smallest index of the smallest Fibonacci number whose decimal notation begins with the given digits. If no Fibonacci number with index smaller than 100000 satisfy that condition, output -1 instead – you think what Fibonacci wants to told you beyonds your ability.
 

Sample Input
15 1 12 123 1234 12345 9 98 987 9876 98765 89 32 51075176167176176176 347746739 5610
 

Sample Output
Case #1: 0 Case #2: 25 Case #3: 226 Case #4: 1628 Case #5: 49516 Case #6: 15 Case #7: 15 Case #8: 15 Case #9: 43764 Case #10: 49750 Case #11: 10 Case #12: 51 Case #13: -1 Case #14: 1233 Case #15: 22374

【题意】求以某个数字开始的斐波拉契数是第多少项。

【参考blog】点击打开链接

【解题方法】

本题询问的数是大数，用字符形式表示，且对应的斐波纳契数列下标可达100000，也很容易加到很大，因此都必须用字符串进行大数加法。同时题目询问的大数不超过40，就是超过40位的时候就应该进行截断处理：只保留高40位，但在实际运算的时候低位可能产生进位，且可能进位是有很远的低位引起的，为了保证正确，必须在运算时保留多余40很多的。
40位一位一位比要比40次，且每次有10种（1到9），不能自己开个hash表否则超内存，又不敢用map可能超时（STL库函数虽方便但效率不高），可以自己建个字典树，最多查找40次，很大优化。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
//gao jingdu
char c[100];
char str[3][110];
void add(char a[],char b[],char bac[])
{
	int x,y,z,up,i,j,k;
	k=up=0;
	i=strlen(a)-1;
	j=strlen(b)-1;
	while(i>=0||j>=0)
	{
		if(i<0) x=0;
		else x=a[i]-'0';
		if(j<0) y=0;
		else y=b[j]-'0';
		z = x+y+up;
		c[k++]=z%10+'0';
		up=z/10;
		i--,j--;
	}
	if(up>0) c[k++]=up+'0';
 	for(int i=0; i<k; i++) bac[i] = c[k-i-1];
	bac[k] = '\0';
}
const int maxs = 10;
typedef struct node{
	int id;
	struct node *next[maxs];
}Trie;
Trie *root;
void Insert(char str[],int idx)
{
	node *t,*s=root;
	int len = strlen(str);
	for(int i=0; i<len&&i<41; i++)
	{
		int id = str[i]-'0';
		if(s->next[id]==NULL)
		{
			t=new node;
			for(int j=0; j<10; j++) t->next[j]=NULL;
			t->id=-1;
			s->next[id]=t;
		}
		s = s->next[id];
		if(s->id<0){
			s->id=idx;
		}
	}
}
int Find(char str[])
{
	int len = strlen(str);
	node *s=root;
	int cnt;
	for(int i=0; i<len; i++)
	{
		int id =str[i]-'0';
		if(s->next[id]==NULL)
		{
			return -1;
		}
		else
		{
			s=s->next[id];
			cnt=s->id;
		}
	}
	return cnt;
}
void Delete(node *p)
{
	for(int i=0; i<10; i++)
	{
		if(p->next[i]!=NULL) Delete(p->next[i]);
	}
	free(p);
}

int main()
{
	root = new node;
	for(int i=0; i<10; i++) root->next[i]=NULL;
	root->id=-1;
	//F[0]=1
	str[0][0]='1';
	str[0][1]=0;
	Insert(str[0],0);
	//F[1]=1
	str[1][0]='1';
	str[1][1]=0;
	Insert(str[1],1);

	for(int i=2; i<100000; i++)
	{
		int len1 = strlen(str[0]);
		int len2 = strlen(str[1]);
		if(len2>60)
		{
			str[1][len2-1]=0;
			str[0][len1-1]=0;
		}
		add(str[0],str[1],str[2]);
		Insert(str[2],i);
		strcpy(str[0],str[1]);
		strcpy(str[1],str[2]);
	}
	char s[60];
	int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s);
		printf("Case #%d: %d\n",cas++,Find(s));
	}
	Delete(root);
	return 0;
}