5
$\begingroup$

Fibonacci words are defined as $F_0 = a, F_1 = b, F_{n+2} = F_nF_{n+1}$ where $a, b$ are letters. How can you find the longest Fibonacci sub-word in a given string? Try to solve it in linear time ($O(n)$).

Example: in a string: BCBAABACB the longest Fibonacci sub-word is BAABA

Improve this question
$\endgroup$
6
  • $\begingroup$ To be clear, are you requesting an algorithm here to solve a general problem? $\endgroup$
    – Rand al'Thor
    Oct 22 at 19:01
  • $\begingroup$ It seems like it… $\endgroup$
    – Someone
    Oct 22 at 19:02
  • 1
    $\begingroup$ It's more about clever thinking than straightforward problems. This falls squarely in the latter category. $\endgroup$
    – Someone
    Oct 22 at 19:13
  • 3
    $\begingroup$ @Someone The two are not necessarily mutually exclusive. Devising an algorithm subject to a complexity constraint often requires considerable creativity. $\endgroup$
    – loopy walt
    Oct 22 at 23:34
  • 1
    $\begingroup$ If the problem is not your own invention you should give some reference. I found it for example here: cstheory.stackexchange.com/questions/29323/fibonacci-words $\endgroup$
    – Herbert Kociemba
    Oct 23 at 9:38

0

Reset to default

Your Answer

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