题目描述：
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
例子：
Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Input: "cbbd" Output: "bb"分析： 题意：给定一个字符串（长度不大于1000），返回它的最长回文连续子串。 思路：这是一道经典的马拉车算法题（Manacher's Algorithm），具体算法细节不再复述，这里给出两个我认为讲得比较清楚的文章链接（感谢博主对算法详细的介绍）： ① 中文版：http://www.cnblogs.com/grandyang/p/4475985.html ② 英文版：https://articles.leetcode.com/longest-palindromic-substring-part-ii/
假设字符串的长度为n，则时间复杂度为O(n))。
代码： #include <bits/stdc++.h> using namespace std; // Manacher's Algorithm // T(n) = O(n) class Solution { public: string longestPalindrome(string s) { int n = s.length(); // Exceptional Case: if(n <= 1){ return s; } // s -> t: "abba" -> "^#a#b#b#a#$" string t = "^"; for(int i = 0; i <= n - 1; i++){ t += ("#" + s.substr(i, 1)); } t += "#$"; // update the center and the right side R n = t.length(); int center = 0, R = 0; int *p = new int[n]; memset(p, 0, sizeof(int) * n); for(int i = 0; i <= n - 2; i++){ p[i] = R > i? min(p[2 * center - i], R - i): 0; while(t[i + p[i] + 1] == t[i - p[i] - 1]){ p[i]++; } if(i + p[i] > R){ center = i; R = i + p[i]; } } // find the maximum element in P center = R = 0; for(int i = 0; i <= n - 2; i++){ if(p[i] > R){ R = p[i]; center = i; } } // get longest palindrome return s.substr((center - R - 1) / 2, R); } };