To have "shortest" expanded palindrome, we should know the longest "heading" palindrome in original string, so that we can reuse as much part as possible. We can make small changes to Manacher algorithm to keep track of the longest heading palindrome.
class Solution { int manacher(string s) { unsigned slen = s.length(); if (slen < 2) return slen; // inserting tokens to original string string ns = "#"; for (int i = 0; i < s.length(); i ++) { char c = s[i]; ns += c; ns += "#"; } // unsigned len = ns.length(); vector<unsigned> rec(len, 0); int maxi = 1, maxr = 0; // for global max umbrella int ci = 1, r = 0; // for current umbrella int hi = 1, hr = 0; // for heading umbrella for (unsigned i = 1; i < len; i++) { int myr = 0; // radius for s[i] // Try to reuse known radius due to symmetry if (i <= (ci + r)) { myr = std::min(rec[2 * ci - i], (ci + r) - i); } // Expand current umbrella from known radius above bool bMis = false; int max_ex = std::min(len - 1 - i, i); while (myr < max_ex) { myr++; if (ns[i + myr] != ns[i - myr]) { bMis = true; break; } } if (bMis) myr--; // Update Records rec[i] = myr; if( (i - myr) == 0) // update heading umbrella { if(myr > hr) { hr = myr; hi = i; } } if ((i + myr) > (maxi + maxr)) // update current umbrella ci = i, r = myr; if (myr > maxr) // update global max umbrella maxi = i, maxr = myr; } return hr; } public: string shortestPalindrome(string s) { int headingPalinLen = manacher(s); string revHead = s.substr(headingPalinLen); std::reverse(revHead.begin(), revHead.end()); return revHead + s; } };
Or, we can apply KMP between s and reserve(s) to find it.. smart idea: https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution