# Easy C++ Manacher

• The idea is to find the longest palindromic substring of `s` that begins with `s[0]`. Then take the remaining susbtring, reverse it and append it to the beginning of `s`.

For example, given `s = "aacecaaa"`, the longest palindromic substring beginning with `s[0] = 'a'` is `"aacecaa"` and the remaining substring is `"a"`. Reverse it and append it to the beginning of `s` gives `"aaacecaaa"`.

For `s = "abcd"`, the longest palindromic substring beginning with `s[0] = 'a'` is `"a"` and the remaining substring is `"bcd"`. Reverse it and append it to the beginning of `s` gives `"dcbabcd"`.

The most difficult part is to implement the Manacher's algorithm to find the longest palindromic substring starting with `s[0]`. Please refer to this nice article if you want to know how it works.

The code is as follows.

``````class Solution {
public:
string shortestPalindrome(string s) {
string t = process(s);
int n = t.length(), center = 0, right = 0;
int* palin = new int[n];
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * center - i;
palin[i] = (right > i) ? min(palin[i_mirror], right - i) : 0;
while (t[i + palin[i] + 1] == t[i - palin[i] - 1])
palin[i]++;
if (i + palin[i] > right) {
center = i;
right = i + palin[i];
}
}
int pos;
for (int i = n - 2; i; i--) {
if (i - palin[i] == 1) {
pos = palin[i];
break;
}
}
string tail = s.substr(pos);
reverse(tail.begin(), tail.end());
return tail + s;
}
private:
string process(string& s) {
int n = s.length();
string t(2 * n + 3, '#');
t[0] = '\$'; t[2 * n + 2] = '%';
for (int i = 0; i < n; i++)
t[2 * (i + 1)] = s[i];
return t;
}
};
``````

Note that this part of the code is just to find the ending position of the longest palindromic substring begining with `s[0]`.

``````int pos;
for (int i = n - 2; i; i--) {
if (i - palin[i] == 1) {
pos = palin[i];
break;
}
}
``````

• thanks, it helps me a lot

• Hi, could you please explain more about "find the ending position " part ? How did you come up it? Thanks :-)

• Hi, that part has no mystery, but just a point of the Manacher's algorithm. This algorithm is not easy to explain and I would like to recommend you to this nice article.

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