• 这个算法有一个很巧妙的地方，它把奇数的回文串和偶数的回文串统一起来考虑了，如果字符串是奇数长度有
  偶数个空，新字符串还是奇数，偶数长度同理。这一点一直是在做回文串问题中时比较烦的地方。这个算法还
  有一个很好的地方就是充分利用了字符匹配的特殊性，避免了大量不必要的重复匹配。
• 通过记录已匹配的最右位置和对应的对称中心来跳过一些没用的比较.
• 算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符，当然这个分隔符要在原串中没有出现过。一
  般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了（见下面的一个例
  子，回文串长度全为奇数了），然后用一个辅助数组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;
            }
        }
    }
  

• p[i] = MIN( p[2 * id-i], mx-i )的解释：
• 当 mx - i > P[j] (j = 2 * id-i)的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，
  由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，
  见下图。
  
• 当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是
  基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会
  扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
  

注明：本文来源于网络，我只是在这里做一个备份。