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  if you want to know how it works.

The code is as follows.

1 class Solution { 2 public: 3     string shortestPalindrome(string s) { 4         string t = process(s); 5         int n = t.length(), center = 0, right = 0; 6         int* palin = new int[n]; 7         for (int i = 1; i < n - 1; i++) { 8             int i_mirror = 2 * center - i; 9             palin[i] = (right > i) ? min(palin[i_mirror], right - i) : 0;10             while (t[i + palin[i] + 1] == t[i - palin[i] - 1])11                 palin[i]++;12             if (i + palin[i] > right) {13                 center = i;14                 right = i + palin[i];15             }16         }17         int pos;18         for (int i = n - 2; i; i--) {19             if (i - palin[i] == 1) {20                 pos = palin[i];21                 break;22             }23         }24         string tail = s.substr(pos); 25         reverse(tail.begin(), tail.end());26         return tail + s;27     }28 private:29     string process(string& s) {30         int n = s.length();31         string t(2 * n + 3, '#');32         t[0] = '$'; t[2 * n + 2] = '%';33         for (int i = 0; i < n; i++)34             t[2 * (i + 1)] = s[i];35         return t;36     }37 };

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

1 int pos;2 for (int i = n - 2; i; i--) {3     if (i - palin[i] == 1) {4         pos = palin[i];5         break;6     } 7 }