主要学习自：http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
问题描述：回文字符串就是左右对称的字符串，如："abba"，而最长回文子串则是字符串长度最长的回文子字符串，如"abbaca"的最长回文子串为"abba"。
常规解法：显而易见采用嵌套循环的方式可以“暴力”结算出答案，其时间复杂度为O(n^2)，而Manacher算法是一种更加省时的算法，其时间复杂度为O(n).
主要思路：
首先使用#（或其他什么符号）填充字符串，并声明一个数组来记录以字符串的每一个字符作为中心，回文字符的半径，使之成为这个样子：
str = # a # b # a # c # a # c # a # b # c # a # c #
arr = 0 1 0 3 0 1 0 3 0 7 0 3 0 1 0 1 0 1 0 3 0 1 0
由此我们可以看出，添加#的作用在于使得字符串无论是奇数长度还是偶数长度，在经过处理后都可以统计以每个字符为中心的回文半径，而偶数长度的回文无法统计这个，如：“abba”
计算出arr后，很容易得到最大回文子串的长度为7，为"bacacab"。
所以这个算法的关键在于计算arr，通过观察我们发现，arr中的数值其实也是对称的：
比如上述例子，以T[11]作为对称中心（回文半径为9），要求T[13]处的回文半径时，可根据其相对于T[11]的对称T[9]来计算，显然arr[13]=arr[9]。可以根据这个例子计算arr[i]=arr[i'].
但是这一方法并不是总是适用的，如：
当i=15时，由于arr[i']>R-i，所以arr[15]不一定等于与之对称的arr[7],如本例中arr[15]=5.因此我们得到以下规律：
if arr[ i’ ] ≤ R – i,
then arr[ i ] ← arr[ i’ ]
else P[ i ] ≥ R – i.
知道了如何计算回文半径，如何确定回文中心呢（即图中的C）？
采用的方式为i+arr[i]>R，则将C替换为i ，R替换为i+arr[i]
直接贴代码：
string preProcess(string str)
{
//$是开头标识，string的结尾标识为\0
string encoded = "$";
int strlen = str.length();
//加#的目的在于使得偶数位的回文字串更加容易辨别，如："1221"，在计算回文长度数组时，不好计算，但$1#2#2#1\0的回文长度(半径)数组为[0,0,0,1,3,1,0,0,0]
for (int i = ; i < strlen; i++)
{
encoded += "#" + str.substr(i,);
}
encoded += "#";
return encoded;
} string longestPalindrome(string str)
{
string temp = preProcess(str);
//回文子串的中心
int palindrome_center = ;
//回文子串的右边界
int right_border = ;
int strlen = temp.length();
//用来存储以该点为中心的回文字符串的半径长度，注意这里是半径长度，因为字符串是经过处理的，包含了#
int * plength_array = new int[strlen];
//i相对于center的对称处
int mirror_i = ;
//循环从1开始因为开头为标示符“$”
for (int i = ; i < strlen; i++)
{
//i相对于回文中心的对称处
mirror_i = * palindrome_center - i;
if (mirror_i>&& right_border > i)//i在回文字符子串内
{
//若范围没有超过右边界，则回文数对称
if (right_border - i > plength_array[mirror_i])
plength_array[i] = plength_array[mirror_i];
else
plength_array[i] = right_border - i;//*先取一个最小值
}
else
plength_array[i] = ;
//针对上面*处先取一个最小值的情况
while (temp[i + + plength_array[i]] == temp[i - - plength_array[i]])
plength_array[i]++;
//如果回文字串的长度超过了现有的右边界，则确立新的中心和右边界
if (i + plength_array[i] > right_border)
{
palindrome_center = i;
right_border = i + plength_array[i];
}
}
//寻找plength_array中的最大元素
int maxlen = ;
//最长回文的中心
int maxlen_center = ;
for (int j = ; j < strlen; j++)
{
if (plength_array[j]>maxlen)
{
maxlen = plength_array[j];
maxlen_center = j;
}
}
delete[] plength_array;
return str.substr((maxlen_center--maxlen)/,maxlen);
}