This is enhanced version of one problem in ICPC WF 2012: https://icpc.kattis.com/problems/fibonacci

Short editorial for WF 2012: http://www.csc.kth.se/~austrin/icpc/finals2012solutions.pdf

I "guess" matrix exponentiation will do the trick for enhanced version (unproven for now, I didn't have time to analyse further).

Let's calculate for each prefix s[1..i] the minimum fibonacci index min_ind[i] such that s[1..i] is a suffix of fib[i] and s[i + 1..n] is a prefix of fib[i + 1].

Because the relation

can be written equivalently as:

it follows that $min_ind[i]$ is either ∞ or less than n (because fib[i] has all the prefixes of fib[i - 2]). After that, it is essentially a linear reccurence of type

for all $\i \geq n$ (or n + 2 or smth.).

You basically have to compute DP[n] and DP[n + 1] and occurences_less_than_inf, and then do matrix exp. I think that should work :).