Codesignal Solution: fibonacciWord
The Fibonacci word sequence of bit strings is defined as:
F(0) = "0"
F(1) = "1"
F(n) = F(n − 1) + F(n − 2) if n >= 2
Where +
is the string concatenation operation.
The first few elements are:
n  p 

0  0 
1  1 
2  10 
3  101 
4  10110 
5  10110101 
6  1011010110110 
Given a number n
and a bit pattern p
, return the number of occurrences of the bit pattern p
in F(n)
.
Example
For n = 6
and p = "10"
, the output should befibonacciWord(n, p) = 5
.
The Fibonacci word for n = 6
is "1011010110110"
, and the string "10"
occurs 5
times in the string "1011010110110"
.
Input/Output
 [time limit] 4000ms (js)

[input] integer n
Guaranteed constraints:
0 ≤ n ≤ 40
. 
[input] string p
The bit pattern you are looking for.
Guaranteed constraints:
0 < p.length ≤ 10^{5}
. 
[output] integer
The number of occurrences of the bit pattern
p
inF(n)
. It is guaranteed that the answer fits in a32
bit integer.
Solution
The given recursive definition of the fibonacci word sequence has a complexity of \(O(2^n)\). However, a linearized dynamic programming algorithm can be derived. Taking the first two elements, every successive element concatenates the last two elements:
n0 = "0" n1 = "1" n2 = n1 + n0 n3 = n2 + n1 n4 = n3 + n2 n5 = ...
This algorithm can be implemented without recursion already:
function fib(n) { a = "0" b = "1" t = "" + n for (; n > 1; n) { t = b + a a = b b = t } return t }
With this function the given table can be reproduced. Now to the interesting part, the counting of the overlapping. Using the derived function above, we could simply loop over the string and count the occurrences of \(p\) at the current position. But with \(n=40\) 165580141 iterations are already needed. So we have a new limiting factor. A better way is to use the point only, where b and a get connected. Looking at the \(P\) last digits of the left string and the \(P\) first digits of the right string  with \(P\) being the length of \(p\)  also prevents doublecountings. Using the function above as a template, we can implement this idea as:
function fibonacciWord(n, p) { a = "0" b = "1" c = p == a r = 0 s = 0 P = p.length  1 for (; n > 1; n) { r = s + c if (P > 0) r+= (b.slice(P) + a.slice(0, P)).indexOf(p) != 1 c = s s = r t = b b = b + a a = t } return r }
Which can be simplified a bit, but unfortunately JavaScript is quite expressive on string slicing and matching, so that the final solution isn't that much shorter:
fibonacciWord = (n, p) => { a = "0" b = "1" c = p == a r = 0 P = p.length  1 while (n) { t = r r+= c + !!P * (b.slice(P) + a.slice(0, P)).includes(p) c = t t = b b+= a a = t } return r }