11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What is the name of this old Czech algorithm textbook ;-) $\endgroup$ – Saeed Jan 29 '15 at 15:23
  • $\begingroup$ Are sub-words required to be contiguous (i.e. factors) in this book? $\endgroup$ – Klaus Draeger Jan 30 '15 at 14:32
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – tarit goswami Aug 29 '18 at 14:29
  • 1
    $\begingroup$ Dynamic programming is an algorithm design technique, not a class of programming languages. $\endgroup$ – David Eppstein Aug 29 '18 at 15:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.