Count how many substrings exist in a Fibonacci string

Ngô Thành Trung 0
Viewed 71

The problem is this:

You are given an integer N and a substring SUB

The Fibonacci String follows the following rules:

F\[0\] = 'A'

F\[1\] = 'B'

F\[k\] = F\[k - 2\] + F\[k - 1\]

(Meaning F\[2\] = 'AB', F\[3\] = 'BAB', F\[4\] = 'ABBAB',...)

Task: Count how many times substring SUB appears in F\[n\]

Sample cases:

Input Output
4 AB 2
6 BAB 4

(N <= 5 * 10^3, 1 <= SUB.length() <= 50)

I had an overall understanding of the problem and wanting to find a more optimal way to solve that problem

My approach is following the fomula F\[k\] = F\[k - 2\] + F\[k - 1\] and then run loop tills it reaches (F\[k\].length - 1), each loop I extract a substring from F\[k\] at i with the same length as SUB (call it F_sub), then I check whether F_sub equals to SUB or not, if yes I increase count (Yes, this approach is not optimal enough for the big tests)

I am also thinking whether Dynamic Programing is suited for this problem or not

fibonacci string algorithm c++
1 Answers

Starting with the first 2 strings that are at least as long as SUB, you should switch the representation of the strings F[n]. Instead of remembering the complete string, you only need to remember 3 numbers:

  1. occurrences: the number of times SUB occurs within the string
  2. prefix: The length of the longest prefix of the string that is a proper suffix of SUB
  3. suffix: The length of the longest suffix of the string that is a proper prefix of SUB

Given o, p, an s for F[k] and F[k+1], you can calculate them for the concatenation F[k+2]:

  • F[k+2].p = F[k].p
  • F[k+2].s = F[k+1].s
  • F[k+2].o = F[k].o + F[k+1].o + JOIN(F[k].s,F[k+1].p)

The function JOIN(a,b) calculates the number of occurrences of SUB within the first a characters of SUB joined to the last b characters of SUB. There are only |SUB|2 values. In fact, since all the values for p and s are copied from the first 2 strings, there are only 4 values of this function that will be used. You can calculate them in advance.

F[N].o is the answer you are looking for.

A straightforward implementation of this takes O(N + |SUB|2), assuming constant time mathematical operations. Since |SUB| <= 50, this is quite efficient.

If the constraint on N was much larger, there's an optimization using matrix exponentiation that could bring the complexity down to O(log N + |SUB|2), but that's not necessary under the given constraints.

Matt Timmermans0
Related