3
$\begingroup$

We define Fibonacci words as: $F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$, $a, b$ can be any symbols.

How can we find the longest Fibonacci sub-word in a given string in linear time?

This question is similar to: Complexity of a naive algorithm for finding the longest Fibonacci substring But I'm in particular interested if there is an $O(n)$ solution.

$\endgroup$

1 Answer 1

1
$\begingroup$

This might be a sledgehammer to crack a nut, but here is my solution.

First let me consider the Fibonacci strings I am used to: $f_{n+2} = f_{n+1} f_n$. Observe that each $f_{n+2}$ is a prefix of the previous $f_{n+1}$. This makes it simple to construct the next Fibonacci string from the previous one. For instance keep a reference to the last prefix and copy that prefix after the current Fibonacci string.

Representing all substrings of a string can be done by constructing the suffix-tree or suffix-array of that string. Magically this suffix-tree $T$ can be constructed in linear time. Start reading Fibonacci string $f_k$ in $T$, and once we have found this string extend the search into $f_{k+1}$, etcetera. This is possible because of the prefix property of Fibonacci strings.

For your definition of Fibonacci strings you can read the search string backwards.

(I had to google the "sledgehammer" idiom; in my native language we "use a canon to shoot at musquitos".)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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