<p>I already posted this question <a href="https://cs.stackexchange.com/questions/28865/complexity-of-a-naive-algorithm-for-finding-the-longest-fibonacci-substring">here</a> but I didn't receive an answer, so I'm posting it here as well :)</p>

<hr>

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

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

<p>with $\star$ denoting string concatenation.</p>

<p>Thus we'll have:</p>

<ul>
<li>$F(0) = \text{b}$</li>
<li>$F(1) = \text{a}$</li>
<li>$F(2) = F(1) \star F(0) = \text{ab}$</li>
<li>$F(3) = F(2) \star F(1) = \text{aba}$</li>
<li>$F(4) = F(3) \star F(2) = \text{abaab}$</li>
<li>...</li>
</ul>

<p>Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any <a href="https://en.wikipedia.org/wiki/Substring" rel="nofollow noreferrer">substring</a> of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.</p>

<h2>The problem</h2>

<p>Given $S$, we want to find its longest Fibonacci substring.</p>

<h3>A trivial algorithm</h3>

<p>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$.</p>

<p>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)$.</p>

<p>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).</p>

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

CC BY-SA 3.0
2015-02-22T21:39:29.567Z
Have you tried manually building a recognizing automaton (NFA or DFA) for the first several Fibonacci strings?
jkff
CC BY-SA 3.0
2015-02-22T22:28:41.283Z
Related: http://cstheory.stackexchange.com/questions/29323
Emil Jeřábek
<ds.algorithms><time-complexity><string-search>
Complexity of a naive algorithm for finding the longest Fibonacci substring
William
# Complexity of a naive algorithm for finding the longest Fibonacci substring

(Asked by: username_0 on 2015-02-22)

I already posted this question [here](https://cs.stackexchange.com/questions/28865/complexity-of-a-naive-algorithm-for-finding-the-longest-fibonacci-substring) 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](https://en.wikipedia.org/wiki/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?

**Tags:** ds.algorithms, time-complexity, string-search
> **Comments:**
> **username_1**: Have you tried manually building a recognizing automaton (NFA or DFA) for the first several Fibonacci strings?  
> **username_2**: Related: http://cstheory.stackexchange.com/questions/29323  

---

## 0 answers

