# Manacher's Algorithm using C++ (8ms)

• ``````class Solution {
public:
int manacher(string& str){
int n = str.length();
vector<int> p(n+1);

int center = 0;
for(int i = 1; i <= n; i ++){
if(i <= center + p[center]){
int j = 2 * center - i;
if(i + p[j] < center + p[center]){
p[i] = p[j];
}else{
int k = center + p[center] + 1;
j = 2 * i - k;

while(j >= 1 && k <= n && str[k-1] == str[j-1]){
k ++;
j --;
}
center = i;
p[i] = k - i - 1;
}
}else{
int k = i + 1;
int j = i - 1;
while(j >= 1 && k <= n && str[j-1] == str[k-1]){
k ++;
j --;
}
center = i;
p[i] = k - i - 1;
}
}

int ret = -1;
for(int i = 1; i <= n; i ++){
if(i - p[i] == 1) ret = max(ret, p[i]);
}
return ret;
}
string shortestPalindrome(string s) {
string str = "#";
int len = s.length();
for(int i = 0; i < len; i ++){
str += s[i];
str += "#";
}

int lsp = manacher(str);
string tmp = s.substr(lsp);
reverse(tmp.begin(), tmp.end());
return tmp + s;
}
``````

};

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