Manacher's Algorithm

 1 string longestPalinderome(string s) {
 2     int N = s.size();
 3     int id = 0, mx = 0;
 4     vector<int> dp(2 * N + 1);
 5     for (int i = 0; i < 2 * N + 1; ++i) {
 6         int j = 2 * id - i;
 7         if (mx > i) {
 8             dp[i] = min(mx - i, dp[j]);
 9         }
10         int left = i - dp[i], right = i + dp[i];
11         for (; left >= 0 && right <= 2 * N; --left, ++right) {
12             if ((left & 1) == 0 || s[left / 2] == s[right / 2]) {
13                 ++dp[i];
14             }
15             else 
16                 break;
17         }
18         if (dp[i] + i > mx) {
19             id = i;
20             mx = dp[i] + i;
21         }
22     }
23     int res = 0;
24     for (int i = 0; i < 2 * N + 1; ++i) {
25         if (dp[i] > dp[res])
26             res = i;
27     }
28     return s.substr(res / 2 - (dp[res] - 1) / 2, dp[res] - 1);
29 }