题目描述： 给你一个字符串，从中找出长度最大的回文字符子串。
思路感想：题目拿到手，上来就蒙了，这一个个比较遍历字符然后再比较是不是回文这不得累死啊。。而且这具体怎么实现也很繁杂，无奈之下，看答案，得到一个动态规划方法。
动态规划思路：依次遍历字符串，每次遍历都检查从第一个字符到当前字符之间的所有字符，需要一个辅助空间，记录每次比较时上一次比较时元素回文的状况，这个值将作为下一次比较时的条件之一，利用了二维数组结构，类似方阵中的下三角形结构，据说还有上三角的题目，有待发现。所以这个题的关键就是构建一个辅助数组，这个数组记录了上一次比较时元素的情况，则当前元素是否回文的情况是元素相等且相邻的那对元素是否为回文（即f[j+1][i-1],i 是从头到尾的索引，一定程度上是指回文串最右边的元素，这样j就是遍历到i的所有元素，可以找到回文串的最左边元素，即开始元素，回文长度即为
i - j +1）,如此循环下去就可以得到最终最长的回文串。
时间复杂度： n方，而且你也可以自己发现，在上面的比较中，有很多都是重复的匹配，在这样的学术探究上，是有很大上升空间的，绝对有某种数学方法是可以避免这样做的，隐约就会感觉到在每次在内部循环的时候应该可以不从0开始，所以这个时候就应该想到要有更加详细的信息，无奈何自己还是想不到，继续看答案。。。
manacher算法：伟大的前人已经想过这个经典的算法，并将其命名为manacher,可怜我们这些无识的人啊，本以为manacher 是个人名或是啥单词，但在有道词典里面竟然没有找到，甚是奇怪，先研究内容好了，在网上找了几篇，怎奈何我这个愚笨的大脑楞是看不懂，在看了第三遍其他人的解析之后才终于有点眉目了。。誓将此题目清晰通俗讲解，为吾辈之小白做贡献（好像有点鄙视后人的意思，请原谅绝对没这个意思。。）好了，这个伟大的算法，其实是怎样的呢，且听我娓娓道来：
1、首先，我们的目标是从一个字符串里面找最长回文串，我们已经了解了一个动态规划的算法，利用辅助数组去记录上一次比较的结果从而判断当前元素的回文情况，里面仅仅是true false 之类的判别信息，于是乎从这里入手，在manacher算法里面，辅助空间不能简单记录是和不是，要记录具体的数值，而这个数值是以当前元素为回文中心向左或向右的距离，而且此时辅助空间也不需要n方，直接为n即可，但是如果你是一个思维敏捷的人，此时就会发现，若是辅助数组记录当前对应元素为中心的回文串的信息，那么就是在说所有的回文串是奇数，而实际上并不是这样的，有偶数的回文串啊，来什么招就挡什么招，不是说有偶数的么，那就在原字符串里间隔加统一的一个字符，这里设为“#”，同时开头和结尾也要特别处理下，这是后话，如此一来，所有的字符自己就一定会有一个回文=》
‘#X#“ 而且所有的回文都是从这个基础上扩展的，也就保证了所有回文是奇数的效果。
2、那么这个关键的辅助数组a[i]是怎样的计算的呢，又是如何减少字符与字符之间的比较次数呢，一个中心，两个基本点，中心就是指当前元素（用i遍历到）然后扩算出去向左向右比较，若相等就将a[i]增1，具体的代码如下：
while(s[i+p[i]] == s[i - p[i]]）p[i]++;
两个基本点，第一个是最长长度maxlength, 这个变量记录你比较时所达到的最长长度，则maxlength = p[i]+i ;第二个是当前元素对应上一个中心点在字符串中的位置 corr = 2*center - 1;(center 并不是每次都跟着i 变化的，它只有在满足一定条件下时才改变成当前i值，所以center会被延迟，具体条件下讲）
3、有了上面的条件这时在去看代码：
void manacher()
{
int i;
int maxlen = 0;
int center;
for(i=1; i<n; i++)
{
if( maxlen > i )
p[i] = MIN( p[2*center-i], maxlen-i );
else
p[i] = 1;
while（str[i+p[i]] == str[i-p[i]]） p[i]++
;
if( p[i] + i > maxlen )
{
maxlen = p[i] + i;
center = i;
}
}
}
每次的p[i] 是通过上次的计算求得的，这是避免多余匹配的关键步骤：
if( maxlen > i )
p[i] = MIN( p[2*center-i], maxlen-i );
这也是最难懂的部分，由于每次遍历时都是找回文串的中心点和回文串的长度，所以当前i元素的回文距离是它相对于中心点对应的位置元素的p[j] ( j = 2*center - 1) 值和 maxlen-i 的最小值，这里假设p[i] >= p[j] ,那就要问了，为什么要找这个对应点呢，我们可以看看下面的图，从别处偷来的。。（谢谢原作者。。）
上图中 id 就是center，假定的回文串中心点，当以其为中心点的时候，其向右向左匹配相等的距离达到了mx,即maxlen，则当下一个元素i进行操作的时候，它的p[i]计算可以从上面的获得，因为maxlen > i， 中间的已经匹配过了，无需在此再匹配，以center 为中心的回文子串中，i 与j 是对应关系，若是回文的，则其相关分布逆向相等，于是若以i 问中心也是回文串的话，则p[i]一定大于等于平p[j] ，而实际上我们并不肯定是否以i 为中心的子串是回文串，需要去匹配i 后面的元素，所以就取其最小值，再进行匹配。
ok，求出p[i]值之后，剩下的事情就是遍历求最大了，就没什么好说的了，希望看到这篇文章的人能对这个算法有所了解。