#237MediumString Matching· KMP on s + separator + reverse(s)

Shortest Palindrome Prefix Completion

A name-plate engraver can add letters only at the **front** of a word, never in the middle or at the end. The customer wants the finished plate to read the same forwards and backwards. Given the word `s`, return the shortest palindrome that can be produced by adding zero or more letters in front of `s`. If more than one palindrome has that length, the answer is unique anyway: the added letters are forced.

Input format

`s`: a string of lowercase letters, possibly empty.

Output format

A string: the shortest palindrome that ends with `s`.

Examples

Input: s = "aacecaaa"

Output: "aaacecaaa"

The longest prefix that is already a palindrome is aacecaa, leaving the last letter a. Adding one a in front gives aaacecaaa.

Input: s = "abcd"

Output: "dcbabcd"

Only the single letter a is a palindromic prefix, so the other three letters must be mirrored in front: dcb + abcd = dcbabcd.

Input: s = "racecar"

Output: "racecar"

The word is already a palindrome, so nothing is added.

Constraints

0 <= s.length <= 5 * 10^4
`s` contains only lowercase English letters.

#strings
#palindrome
#kmp
#prefix-function