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?