Shortest Palindrome by Adding in Front
hardStrings II+40 XPTime limit 2s
You may add characters only at the front of a string. Make it a palindrome using as few added characters as possible, and print the resulting palindrome. aacecaaa becomes aaacecaaa (one a added), and abcd becomes dcbabcd.
Input: one line with a string of lowercase letters.
Output: the shortest palindrome that ends with the given string.
Constraints: 1 ≤ length ≤ 10⁵.
Think about it: you keep the longest prefix that is already a palindrome, and add the reverse of the rest in front. Testing each prefix is O(n²). Instead build s + '#' + reverse(s) and compute its prefix function: the last value is exactly the length of the longest palindromic prefix (it is a prefix of s that equals a suffix of reverse(s)).
Sample input 1
aacecaaa
Sample output 1
aaacecaaa
Sample input 2
abcd
Sample output 2
dcbabcd
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).