[百度]2014百度校园招聘之最长回文串

给你一个字符串，找出该字符串中对称的子字符串的最大长度。即求最大回文串。

即不使用技巧，穷举所有可能。时间复杂度为o(n^3)（时间上最长，不推荐使用），空间复杂度为o(1)。

本思路是从最大长度的字串开始，而不是从最小开始。假如说给定的字符串为len，先遍历长度为len的字串是否为回文串，如果是停止，

如果不是遍历长度为len-1的字串是否是回文串，一次类推。

假设现在已经遍历到第 i 个字符，要找出以该字符为“中心”的最长对称字符串，我们需要用另两个指针分别向前和向后移动，直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况，所以需要写出两种情况下的代码：

（1） 第 i 个字符是该对称字符串的真正的中心，也就是说该对称字符串以第 i 个字符对称， 比如： “aba”

（2）第 i 个字符串是对称字符串的其中一个中心。比如“abba”。

所以遍历到每个字符都要考虑两种情况，它可能是在奇数个回文串中或者是在偶数个回文串中

算法的基本思路是这样的：把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶)，同时为了防止越界，在字符串的首部也加入一个特殊符$，但是与分隔符不同。同时字符串的末尾也加入'\0'。算法的核心：用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1，此时回文字符串就是字符串本身。 

示例：原字符串 'abba’，处理后的新串 ' $#a#b#b#a#\0’，得到对应的辅助数组p=[0,1,1,2,1,2,5,2,2,1]。 

详细请看：[算法]manacher算法之最大回文子串

相关链接：

[小米]2015小米校招之回文数判断

[网易]字符串回文分割