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

  • $\begingroup$ To be clear, are you requesting an algorithm here to solve a general problem? $\endgroup$ Commented Oct 22, 2023 at 19:01
  • $\begingroup$ It seems like it… $\endgroup$
    – Someone
    Commented Oct 22, 2023 at 19:02
  • 1
    $\begingroup$ It's more about clever thinking than straightforward problems. This falls squarely in the latter category. $\endgroup$
    – Someone
    Commented Oct 22, 2023 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
    Commented Oct 22, 2023 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$ Commented Oct 23, 2023 at 9:38


Your Answer

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