Problem 2- Fibonacci word sequence

PROBLEM 2 The Fibonacci word sequence of bit strings is defined as:

F(n) =

Here + denotes concatenation of strings. The first few elements are:

n	F(n)
0	0
1	1
2	10
3	101
4	10110
5	10110101
6	1011010110110
7	101101011011010110101
8	1011010110110101101011011010110110
9	1011010110110101101011011010110110101101011011010110101

Given a bit pattern p and a number n, how often does p occur in F(n)?

Input 

The first line of each test case contains the integer n (0n100). The second line contains the bit pattern p. The pattern p is nonempty and has a length of at most 100 000 characters.

Output 

For each test case, display its case number followed by the number of occurrences of the bit pattern p in F(n). Occurrences may overlap. The number of occurrences will be less than 2⁶³.

Sample Input 

6
10
7
10
6
01
6
101
96
10110101101101

Sample Output 

Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428

Scroll down for answer:




































//--------------main class

package

fib;

import

java.io.InputStreamReader;

import

java.util.Scanner;

public

class Fibonacci {

/**

*

@param args

*/

public static void main(String[] args) {

int n;

int occurrance;

String numString;

String pattern;

Scanner scan =

new Scanner(new InputStreamReader(System.in));

System.

out.println("Enter Number");

n = scan.nextInt();

numString = Creator.createString(n);

System.

out.println(n + "=" + numString);

System.

out.println("{EXTRAINFO: The representation requires " + numString.length()

+

" bits]");

// take aid of file for displaying non-visible strings on console

// Creator.writeTofile(numString);

System.

out.println("enter Pattern:");

pattern = scan.next();

// find number of occurrence of given pattern in this string

occurrance = Creator.matchPattern(numString, pattern);

System.

out.println("pattern " + pattern + " has occurred " + occurrance

+

" times");

}

}
//-------------------2nd class

package

fib;

import

java.io.File;

import

java.io.FileOutputStream;

import

java.io.IOException;

public

class Creator {

public

static String createString(int n) {

if

(n == 0)

return

"0";

else

if (n == 1)

return

"1";

else

return

"" + createString(n - 1) + createString(n - 2);

}

public

static void writeTofile(String s) {

File f =

new File("D:\\text.txt");

try

{

f.createNewFile();

FileOutputStream fos =

new FileOutputStream(f);

fos.write(s.getBytes());

}

catch (IOException e) {

//

TODO Auto-generated catch block

e.printStackTrace();

}

}

public

static int matchPattern(String numString, String pattern) {

int

count = 0;

int

pos = 0;

String replaceWith =

"";

int

patternLength = pattern.length();

for

(int i = 0; i < patternLength; i++) {

replaceWith +=

"x";

}

int

lastIndex = numString.lastIndexOf(pattern);

while

(pos < lastIndex) {

pos = numString.indexOf(pattern);

count++;

numString = numString.replaceFirst(pattern, replaceWith);

}

return

count;

}

}

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