1282

Theory:

The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3) that is longer than the pattern.

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdlib>

#define INF 1000000
#define ll long long

using namespace std;

ll fib[105];
string Fib[105];
vector<int> vb;
int *failureFunc;
void kmpsearch(string p,string s,int min_index)
{
	int i=1,len=0;
	int length = p.size();
	//int failureFunc[length];
	failureFunc=(int *)malloc(sizeof(int)*length);
	failureFunc[0]=0;

	while(i<length)
	{
		if(p[i]==p[len])
		{
			len+=1;
			failureFunc[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len=failureFunc[len-1];
			}
			else
			{
				failureFunc[i]=0;
				i+=1;
			}
		}
	}

	int I = s.size();
	i=0;len=0;
	vb.clear();
	while(i+len<I)
	{
		if(i>fib[min_index-1])
		break;
		if(p[len]==s[i+len])
		{
			if(len==length-1)
			{
				vb.push_back(i);
			}
			else
			{
				len+=1;
				continue;
			}

		}
		if(len)
		{
			i=i+len-failureFunc[len-1];
			len=failureFunc[len-1];
		}
		else
		{
			i+=1;
		}
	}

}
void findAt(int min_indx,string p)
{
	kmpsearch(p,Fib[min_indx],min_indx);
}
int main()
{
	int n;
	int kase=1;
	string pat;
//	string prev,prev1,tmp;

	fib[0]=1;fib[1]=1;
	Fib[0]="0";Fib[1]="1";
	for(int i=2;i<104;i++)
		fib[i]=min(fib[i-1]+fib[i-2],9223372036854775805LL);

	int ii;
	for(ii=1;ii<3 || Fib[ii-3].size()<100000;ii++)
	{
		Fib[ii+1]=Fib[ii];
		Fib[ii+1].append(Fib[ii-1]);
	}

	while(scanf("%d",&n)!=EOF)
	{
		cin>>pat;
		if(pat=="0")
		{
			if(n==1)
			cout<<"Case "<<kase++<<": "<<0<<"\n";
			else if(n==0)
			cout<<"Case "<<kase++<<": "<<1<<"\n";
			else
			cout<<"Case "<<kase++<<": "<<fib[n-2]<<"\n";
			continue;
		}
		else if(pat=="1")
		{
			if(n==1)
			cout<<"Case "<<kase++<<": "<<1<<"\n";
			else if(n==0)
			cout<<"Case "<<kase++<<": "<<0<<"\n";
			else
			cout<<"Case "<<kase++<<": "<<fib[n-1]<<"\n";
			continue;
		}
		else
		{
			int min_idx=3;
			while(fib[min_idx-3]<=pat.size())
				min_idx+=1;
			if(min_idx>n)
			min_idx=n;
			findAt(min_idx,pat);

			ll prev=0,suf=0;
			ll overlap[2]={0,0};
			int j,k;
			int sz=pat.size();
			for(int i=0;i<vb.size();i++)
			{
				j=vb[i];
				k=j+sz-1;
				if(j<fib[min_idx-2])
				{
					if(k<fib[min_idx-2])
					{
						prev+=1;
					}
					else
					overlap[0]+=1;
				}
				else if(j<fib[min_idx-1])
				{
					if(k<fib[min_idx-1])
					suf+=1;
					else
					overlap[1]+=1;
				}
			}

			int f=1;
			ll tmp;
			for(int i=0;i<=n-min_idx+1;i++)//for(int i=min_idx-1;i<=n;i++)
			{
				f=1-f;
				tmp=prev;//initially f(n-2)
				prev=prev+suf+overlap[f];//initially this f(n-1)
				suf=tmp;
			}
			cout<<"Case "<<kase++<<": "<<prev<<"\n";
		}

	}
	return 0;
}