Efficiently Finding Shortest Palindromes With KMP Algorithm

214. Shortest Palindrome
Difficulty: Hard
Topics: String, Rolling Hash, String Matching, Hash Function
You are given a string s. You can convert s to a palindrome1 by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 104
s consists of lowercase English letters only.

Solution:
We need to find the shortest palindrome by adding characters in front of a given string. We can approach this by identif...