Shortest Palindrome Extension

Given a string s, your task is to compute the shortest palindrome that can be formed by adding characters in front of s. A palindrome is a string that reads the same forwards and backwards. The efficient solution to this problem can be achieved using the Knuth-Morris-Pratt (KMP) algorithm to identify the longest palindromic prefix.

For example:

• Input: abcd → Output: dcbabcd
• Input: aacecaaa → Output: aaacecaaa
• Input: abc → Output: cbabc

It is required that your solution reads from standard input (stdin) and writes the result to standard output (stdout). If the input string is empty, then the output should also be an empty string.

The key insight is to find the longest prefix of s that is a palindrome. Then, the remaining suffix is reversed and prepended to s to form the shortest palindrome.

Mathematically, if lps is the length of the longest palindromic prefix, then the shortest palindrome is given by:

$$\text{result} = \text{reverse}(s[(lps):]) + s$$

inputFormat

The input consists of a single line containing the string s (which may be empty). It is read from standard input.

outputFormat

Output a single line containing the shortest palindrome formed by adding characters to the beginning of s. The output should be written to standard output.

## sample

abcd

dcbabcd

</p>