Description
Given a string s, find the shortest palindrome by adding characters in front of it. Use KMP failure function for O(n) solution.
Examples
Input:
s = "aacecaaa"Output:
"aaacecaaa"Explanation:
Add 'a' in front to make it a palindrome.
Input:
s = "racecar"Output:
"racecar"Explanation:
The string is already a palindrome, so no characters need to be added in front.
Input:
s = "abcde"Output:
"edcbabcde"Explanation:
To make it a palindrome, the reverse of 'bcde' (which is 'edcb') is added in front, resulting in 'edcbabcde'.
Constraints
- •
0 ≤ s.length ≤ 5 * 10⁴