Naive algorithm (TLE)
The question can be thought of as finding the longest palindrome starting from index 0. The answer could then be found by appending reverse of the remaining string at the beginning. For instance, if the string is abacd then longest palindrome starting from index 0 is aba. Appending reverse of the remaining string at the beginning gives us the answer: dcabacd.
// Naive algorithm to check each substring starting from index 0 for palindrome
string shortestPalindrome(string s) {
int endIdx = 0;
for (int i=0; i<s.length(); i++) {
if (isPalindrome(s, 0, i))
endIdx = i;
}
string ans = "";
for (int i=s.length()-1; i>endIdx; i--)
ans += s[i];
ans += s;
return ans;
}
bool isPalindrome (string s, int l, int h) {
while (l<h) {
if (s[l]==s[h]) {
l++;
h--;
continue;
}
return false;
}
return true;
}
There can be n such subtrings and the isPalindrome() function takes O(string length) time. String length goes from 1..n so total time is 1 + 2 + .. + n = O(n^2)
This gives TLE for large inputs.
Using the KMP table
If we have the reverse of the string, then checking if str[0..i] is a palindrome is checking if str[0..i] is equal to reverse_str[n…n-i]. See this for example:
String: abacd
Reverse: dcaba
We start iterating the actual string from the beginning and the reverse string from the end, when they are equal, it means we have found a palindrome. Unfortunately, checking if two strings are “equal” taken O(string length) time as well so it is no better than the naive solution.
The KMP preprocessing table finds the longest prefix which is also a suffix of the string for every string [0..i] in O(n) time.
Let us append the reverse of the original string to the original string with a divider (say #) like this: abacd#dcaba
Now, all we need to do is to find the length of the longest prefix which is also a suffix for the whole string (aba in this case). Note that it cannot be greater than the length of the original string (say n) because of the ‘#’ (assuming original string only contains alphabets).
// Applying KMP
string shortestPalindrome(string s) {
string temp = s;
reverse(begin(temp), end(temp));
temp = s + "#" + temp;
// KMP table
vector<int> table(temp.length(), 0);
int anchor=0;
for (int i = 1; i<temp.length();) {
if (temp[i] == temp[anchor]) {
table[i] = ++anchor;
i++;
} else {
if (anchor == 0) {
table[i] = 0;
i++;
} else {
anchor = table[anchor-1];
}
}
}
temp = s.substr(table[temp.length()-1]);
reverse(begin(temp), end(temp));
return temp + s;
}
Also see solution using Robin-Karp rolling hash by @lixx2100 here.