The solution solves the problem within time limit but there are better solutions, by sorting the array using counting sort might give a better timing. There is also a solution without using a suffix array , simply by adding the string with itself and comparing which one is the lowest sub string.







Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)




This problem also can be solved using Suffix array but gets TLE. Code as follows: