StringKMPPattern Matching
You may add characters only at the front of a string. Find and print the shortest palindrome you can make this way.
Input
A single string of lowercase letters.
Output
Print the shortest palindrome that can be formed by adding characters in front.
Constraints
1 <= length <= 5 * 10^4
Example 1
Input
aacecaaa
Output
aaacecaaa
The prefix aacecaa is already a palindrome, so only one a is added.
Example 2
Input
abcd
Output
dcbabcd
Only the first letter is a palindromic prefix, so dcb goes in front.