<p>The obvious way to go is dynamic programming: let $F(i,j)$ store the two letters for which a Fibonacci word of order $i$ starts at position $j$, and calculate this by looking at $F(i-2,j)$ and $F(i-1,j+\operatorname{fib}(i))$. This takes $O(n \log n)$ time at most, because there are only logarithmically many possible values of $i$.</p>

<p>But I suspect that there can only be $O(n/\operatorname{fib}(i))$ positions for which $F(i-2,j)$ is nonempty (i.e. that when two Fibonacci words of the same length are present they can only overlap for up to a constant fraction of their length rather than most of their length). The nonempty positions of $F(i-2,j)$ are the only ones for which you need to do the (constant time) calculation for $F(i,j)$. So if my suspicion is true then you could speed it up to $O(n)$ by keeping track of a list of nonempty positions for each value of $i$ and using the list for $i-2$ to speed up the computation of the list for $i$.</p>

<p>If you store $F$ in an array the space would still be $O(n \log n)$ even after the speedup but this could be improved using a hashtable instead. Or alternatively you could store $F$ in a bit-packed array with $O(n)$ $\log n$-bit words (using the observation that you only need to know whether it's empty or not; you can find the two characters for each substring by looking at the first two of its positions in the input string).</p>

CC BY-SA 4.0
2018-08-29T14:29:57.507Z
Can you tell me, why you thought that *dynamic programming* will be best choice for this problem? Where we will face problem if we use any static programming like **C** ?
tarit goswami
CC BY-SA 4.0
2018-08-29T15:56:10.303Z
Dynamic programming is an algorithm design technique, not a class of programming languages.
David Eppstein
CC BY-SA 3.0
2015-01-29T16:17:44.240Z
2015-02-23T16:50:14.257Z
2015-02-23T16:50:14.257Z
David Eppstein
<p>I came across the following problem in my old Czech algorithm textbook, sadly came with no hints or solution.</p>

<p>"We define Fibonacci words as $F_{0}=a$, $F_{1}=b$, $F_{n+2}=F_{n}F_{n+1}$, where $a$ and $b$ are general letters. How in a given string (over a potentially large alphabet) can you find the longest Fibonacci's sub-word in linear time?"</p>

<p>I know a solution in quadratic time, but can't reduce it to linear. Can anyone point me to the right direction?</p>

CC BY-SA 3.0
2015-01-29T15:23:27.053Z
What is the name of this old Czech algorithm textbook ;-)
Saeed
CC BY-SA 3.0
2015-01-30T14:32:54.933Z
Are sub-words required to be contiguous (i.e. factors) in this book?
Klaus Draeger
<string-matching><string-search>
Fibonacci words
Fanda
# Fibonacci words

(Asked by: username_0 on 2015-01-29)

I came across the following problem in my old Czech algorithm textbook, sadly came with no hints or solution.

"We define Fibonacci words as $F\_{0}=a$, $F\_{1}=b$, $F\_{n+2}=F\_{n}F\_{n+1}$, where $a$ and $b$ are general letters. How in a given string (over a potentially large alphabet) can you find the longest Fibonacci's sub-word in linear time?"

I know a solution in quadratic time, but can't reduce it to linear. Can anyone point me to the right direction?

**Tags:** string-matching, string-search
> **Comments:**
> **username_1**: What is the name of this old Czech algorithm textbook ;-)  
> **username_2**: Are sub-words required to be contiguous (i.e. factors) in this book?  

---

## 1 answers

### Answer by username_3 on 2015-01-29. Score: 12 | Accepted answer

The obvious way to go is dynamic programming: let $F(i,j)$ store the two letters for which a Fibonacci word of order $i$ starts at position $j$, and calculate this by looking at $F(i-2,j)$ and $F(i-1,j+\operatorname{fib}(i))$. This takes $O(n \log n)$ time at most, because there are only logarithmically many possible values of $i$.

But I suspect that there can only be $O(n/\operatorname{fib}(i))$ positions for which $F(i-2,j)$ is nonempty (i.e. that when two Fibonacci words of the same length are present they can only overlap for up to a constant fraction of their length rather than most of their length). The nonempty positions of $F(i-2,j)$ are the only ones for which you need to do the (constant time) calculation for $F(i,j)$. So if my suspicion is true then you could speed it up to $O(n)$ by keeping track of a list of nonempty positions for each value of $i$ and using the list for $i-2$ to speed up the computation of the list for $i$.

If you store $F$ in an array the space would still be $O(n \log n)$ even after the speedup but this could be improved using a hashtable instead. Or alternatively you could store $F$ in a bit-packed array with $O(n)$ $\log n$-bit words (using the observation that you only need to know whether it's empty or not; you can find the two characters for each substring by looking at the first two of its positions in the input string).

> **Comments:**
> **username_4**: Can you tell me, why you thought that *dynamic programming* will be best choice for this problem? Where we will face problem if we use any static programming like **C** ?  
> **username_3**: Dynamic programming is an algorithm design technique, not a class of programming languages.  

---

