# C++ 6ms solution, using KMP algorithm

• class Solution {
public:
string shortestPalindrome(string s) {
if (s.size()<=1) return s;
string srv=s;
reverse(srv.begin(),srv.end());
if (srv==s) return s;
vector<int> next(srv.size(),0);
int i=1,j=0;
while(i<srv.size()){
if (srv[i]==s[j]){
next[i]=j+1;
i++;j++;
}else if (j>0){
j=next[j-1];
}else{
next[i]=0;i++;
}
}
int k=next.back();
string res="";
for (int i=s.size()-1;i>=k;i--){
res+=s[i];
}
res+=s;
return res;
}
};

• There's a problem with most of the KMP based solutions. Try input "aacecaaazz". Output should be "zzaacecaaazz"
Leetcode OJ probably doesn't check these cases.

• Yes, you are right. There is a bug in the code. Thanks for pointing it out. Good news is I no longer use KMP for this problem. The following straightforward code is much easier to explain in an interview.

string shortestPalindrome(string s) {
if (s.size()<=1) return s;
int sz =s.size();
int maxSize = 0;
for (int i=sz/2;i>=0;){
int j=i;
while (i<sz-1 && s[i]==s[i+1]) i++;
while (j>0 && s[j]==s[j-1]) j--;
int k=0;
while (j-k>=0 && i+k<sz && s[i+k]==s[j-k]) k++;
if (j-k==-1) {
maxSize = i+k;
break;
}
i=j-1;
}
string s2 = s.substr(maxSize);
reverse(s2.begin(),s2.end());
return s2+s;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.