Let's make string s = rstr + # + str, where str is given string, rstr is reversed str. You can take every char on the place of "#", the main thing that this char was not in str. Then compute prefix function of it, then we just need take last value PR in array, this number will show length of the longest suffix of str, which is palindromic. One can prove it. Next step of algorithm is obvious: output str and first len - PR in reverse order as I alredy said.