本文共 2174 字，大约阅读时间需要 7 分钟。
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 }
转载地址：http://mfqko.baihongyu.com/