Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: "aacecaaa" Output: "aaacecaaa" Example 2:
Input: "abcd" Output: "dcbabcd"
/*
So what we are doing here is consider a string "ananab" so if we reverse it and add it beginning then we will get
the palindrom that is banana ananab but that's not the smallest . Why is it long? becuase of "anana" substring
"anana" itself is a substring so we don't need to append that . So we need to find out the longest common prefix
string and its reverse so that we can remove that prefix and add the remaining to the string. For example
Longest comon prefix is anana from starting of String s so after removing anana from the reverse we have "b"
we add that "b" in start.
SO in layman terms we need to find the longest palindromic substring from start and then add the rest of string
reverse in the beginnging so How do we find the longest palindromic substring from the beginning . That's where
KMP comes in. So as we reverse the string it becomes a pattern matching problem where we are finding longest
common prefix with suffix of reverse that will just give us the palindromic substring.
*/
class Solution {
public String shortestPalindrome(String s) {
String rev=new StringBuilder(s).reverse().toString();
String newString=s+"#"+rev;
int n=newString.length();
//Building KMP Array
int[] arr=new int[n];
for(int i=1;i<arr.length;i++){
int t=arr[i-1];
while(t>0 && newString.charAt(i)!=newString.charAt(t)){
t=arr[t-1];
}
if(newString.charAt(i)==newString.charAt(t)) ++t;
arr[i]=t;
}
return rev.substring(0,s.length()-arr[n-1])+s;
}
} //banana ananab