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[j1];
}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;
}
};
C++ 6ms solution, using KMP algorithm


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<sz1 && s[i]==s[i+1]) i++; while (j>0 && s[j]==s[j1]) j; int k=0; while (jk>=0 && i+k<sz && s[i+k]==s[jk]) k++; if (jk==1) { maxSize = i+k; break; } i=j1; } string s2 = s.substr(maxSize); reverse(s2.begin(),s2.end()); return s2+s; }