1.最长回文子串的求解很容易可以枚举每一个i，然后从i开始向两头匹配找以i为中心的最大回文串（注意要分偶数长和奇数长），很明显这是o(n2)的算法；
2.另外也很容易想到dp的解法：首先构造原串s的逆串rs，则以dp[i][j]表示 suffix(s,i)和suffix(rs,j)的最大长度，很明显当 s[i] == rs[j]时候，dp[i][j]=dp[i-1][j-1]+1,否则dp[i][j]= max(dp[i][j-1],dp[i-1][j])，这也是o(n2)的，但是还需要o(n2)的空间；
3.也可以用后缀数组求解，即根据原串 s构造新的字串 ns=s#s，注意中间用于连接的字符要小于s中的所有字符，然后对ns构造后缀数组，排序，然后计算排序数组中相邻子串的最大相似长度，即得。这是o(nlogn)的解法，具体可参考后缀数组的论文；
4.后来去网上找了o(n)的解法：
来自：http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474
但是该文中对 算法中很重要的一个不等式解释地不清楚，这里记下自己的理解：（请先阅读原文）
首先前面的内容直接截自原文：
首先：大家都知道什么叫回文串吧，这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在O（n）的时间复杂度内既线性时间复杂度的情况下，求出以每个字符为中心的最长回文有多长，
这个算法有一个很巧妙的地方，它把奇数的回文串和偶数的回文串统一起来考虑了。这一点一直是在做回文串问题中时比较烦的地方。这个算法还有一个很好的地方就是充分利用了字符匹配的特殊性，避免了大量不必要的重复匹配。
算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符，当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了（见下面的一个例子，回文串长度全为奇数了），然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。P［id］记录的是以字符str［id］为中心的最长回文串，当以str［id］为第一个字符，这个最长回文串向右延伸了P［id］个字符。
原串： w aa bwsw f d
新串： # w # a # a # b # w # s # w # f # d #
辅助数组P： 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
这里有一个很好的性质，P［id］-1就是该回文子串在原串中的长度（包括‘#’）。如果这里不是特别清楚，可以自己拿出纸来画一画，自己体会体会。当然这里可能每个人写法不尽相同，不过我想大致思路应该是一样的吧。
好，我们继续。现在的关键问题就在于怎么在O（n）时间复杂度内求出P数组了。只要把这个P数组求出来，最长回文子串就可以直接扫一遍得出来了。
由于这个算法是线性从前往后扫的。那么当我们准备求P［i］的时候，i以前的P［j］我们是已经得到了的。我们用mx记在i之前的回文串中，延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。（注：为了防止字符比较的时候越界，我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’，故我的新串下标是从1开始的）
好，到这里，我们可以先贴一份代码了。
void pk()
{
int i;
int mx = 0;
int id;
for(i=1; i<n; i++)
{
if( mx > i )
p[i] = MIN( p[2*id-i], mx-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
if( p[i] + i > mx )
{
mx = p[i] + i;
id = i;
}
}
}
注意 if (mx > i ) p[i] = MIN ( p [2 * id- j ] , mx - i )；这条语句解释如下：
1.这条语句是为了在计算 p[i] 时不要从头算起，而是根据前面已经计算过的信息得到 p[i] 至少具有的一个下限；
2. 令 j= 2* id -i ; j 表示以 id为中心与 i 对称的位置，另 lmx为mx以id为中心对称的点，很明显 lmx < j的；
3. 如果 p [ j ] <= j- lmx ; 即以 j 为中心的回文串不会超过 lmx，即p[j]表示的回文串在 p [id]表示的回文串的内部，那么有 i 与 j是对称且均包含于 p[id]的回文串里，那么由回文串的定义，很明显 p[i] 左右的子串与 p[j]左右的子串是相等的，即 p[i]的下限至少为p[j]；
4.如果 p[j] > j- lmx，即j为中心的回文串超出了p[id]表示的回文串，由i和j的对称，我们只知道 i->mx与 lmx->j 这段是相等的，而超出mx的部分的字符我们还未探测到，所以无法确定，所以 p[i]此时的下限只能确定是 p[i] > = mx -i ；
所有可得 上面的不等式。