原题链接：https://leetcode.com/problems/longest-palindromic-substring/
Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic substring.
char* longestPalindrome(char* s) {<span style="white-space:pre"></span>//细节实现上应该还可以优化int i = 0, j = 1, len = 0, maxCenter = 0;int center = 0, maxRight = 0;char extendS[2002] = {};int lenMax[2002] = {};//记录每个字符为中心的最长回文子串对称字符对数while (s[i] != '\0') {//将字符串最左边最右边及每两个字符之间填充字符‘#’，扩充至奇数个，避免分类讨论extendS[len++] = '#';extendS[len++] = s[i++];}extendS[len++] = '#';for (i = 1; i < len; ++i) {//如果当前字符关于center对称的字符的回文串没有超出center回文串范围，则对称两处的回文串长度也是对称的if (2 * center – i >= 0 && 2 * center – i – lenMax[2 * center – i] > 2 * center – maxRight) {lenMax[i] = lenMax[2 * center – i];}else {while (i – j >= 0 && i + j < len && extendS[i + j] == extendS[i – j])++j;lenMax[i] = j – 1;center = i;maxRight = i + j – 1;j = 1;if (lenMax[i] > lenMax[maxCenter])maxCenter = i;}}s[(maxCenter + lenMax[maxCenter]) / 2] = '\0';//最大回文子串的结尾后面设置结束字符return s + (maxCenter – lenMax[maxCenter]) / 2;}
manacher算法核心：
1.字符之间填充原字符集不存在的字符（#），使总长度达到2n+1，避免了偶数个和奇数个的分类情况；
2.维护一个2n+1的整型数组，里面的数据记录以扩充字符串中对应字符为中心的最长回文字串。如“#a#a#b#“，则L[]={0,1,2,1,0,1,0}。（为了简化回文串长度与字符间位置关系的线性关系，这里记录回文串对称的字符对）；只要依次求出每个字符的L[]值，遍历数组就可以找到最长子回文串。
3.回文字符串的一个性质：回文字符串的子串的回文特性是对称的。如回文串”abacaba“，L[1]和L[5]、L[2]和L[4]都是相等的，，即知道L[1]可以不用计算L[5]，这是算法能实现O(N)时间复杂度的关键所在。这里需要注意的是：“babcbac”。虽然abcba是回文串，但是两个a的L值是不相等的，因为L(1)记录的回文子串超出了abcba的边缘，已经不再具有对称性。
有时间，我们可以去爬山，
