A palindrome is a word that is its own reverse. I will define the left palindromic root of a word as the shortest prefix of the word for which the shortest possible palindrome that begins with that prefix is the original word. So the left palindromic root of
race and the left palindromic root of
The second case may not seem obvious at first, so consider this table:
Prefix | Shortest palindrome with same prefix | "" | "" "A" | "A" "AB" | "ABA" "ABB" | "ABBA" "ABBA" | "ABBA"
Since the shortest prefix which maps to
ABB, it is the left palindromic root of
The process of converting from a prefix to the minimum palindrome is also called the left palindromic closure, as can be found in this related challenge.
Write the shortest code that, given a palindrome as input, returns the shortest palindrome that begins with the reverse of the left palindromic root of the input. Equivalently, find the left palindromic closure of the reverse of the left palindromic root of the input.
You may assume the input is part of some arbitrary alphabet, such as lower-case ASCII or positive integers, as long as it does not trivialise the challenge.
girafarig -> farigiraf farigiraf -> girafarig racecar -> ecarace ABBA -> BBABB -> a -> a aa -> aa aba -> bab aaa -> aaa 1233321 -> 333212333 11211 -> 2112 ABABA -> BABAB CBABCCBABC -> CCBABCC
You can make additional cases using this program.