Add characters to the front of s to make it a palindrome. Return shortest result.
Input: s="aacecaaa" → Output: "aaacecaaa"
Input: s="abcd" → Output: "dcbabcd"
Use KMP to find the longest palindrome prefix. Append reverse of remaining suffix to front.
- Construct string: s + "#" + reverse(s)
- Apply KMP failure function to this combined string
- Last value of lps = length of longest palindrome prefix
- Add reverse of s[lps..] to the front of s
public String shortestPalindrome(String s) {
String rev = new StringBuilder(s).reverse().toString();
String combined = s + "#" + rev;
int n = combined.length();
int[] lps = new int[n];
for (int i = 1, len = 0; i < n; ) {
if (combined.charAt(i) == combined.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len-1];
else lps[i++] = 0;
}
int longest = lps[n-1];
return rev.substring(0, s.length() - longest) + s;
}
- Time Complexity: O(n)
- Space Complexity: O(n)