I already posted this question here but I didn't receive an answer, so I'm posting it here as well :)

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:

$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2) &\mbox{else} \end{cases} $$

with $\star$ denoting string concatenation.

Thus we'll have:

  • $F(0) = \text{b}$
  • $F(1) = \text{a}$
  • $F(2) = F(1) \star F(0) = \text{ab}$
  • $F(3) = F(2) \star F(1) = \text{aba}$
  • $F(4) = F(3) \star F(2) = \text{abaab}$
  • ...

Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any substring of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.

The problem

Given $S$, we want to find its longest Fibonacci substring.

A trivial algorithm

For each position $i$ of the string $S$, suppose that $F(2)$ starts there (it's enough to check that the $i$-th and $(i+1)$-th symbols are distinct). If that's the case, check if it can be extended to $F(3)$, then $F(4)$, and so on. After that, start again from the position $i+1$. Repeat until you reach the position $n$.

We must look at each symbol at least once, so it's $\Omega(n)$. There are only two for loops involved, so we can furthermore say that it's $O(n^2)$.

However (somewhat unsurprisingly) this naive algorithm performs much better than usual quadratic algorithms (if it does a lot of work on the $i$-th position, it won't do a lot of work in the next positions).

How can I use Fibonacci properties to find tighter bounds for the execution time of this algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.