最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

分析:参考马拉车算法

由于回文串长度可奇可偶,如:bob,noon,为了统一处理,马拉车算法的第一步是做预处理,将源串字符串的前后都加上#.

bob    -->    #b#o#b#
noon    -->    #n#o#o#n# 

这样做的好处是无论源串回文串长度是奇数还是偶数,新串的回文串长度都是奇数,这样就无需分情况讨论了.

设:

1. 源串最长回文子串:起始位置为beg,长度为len,
2. 新串最长回文子串: 圆心为maxCenter,半径为maxLen,

通过分析有:

1. len = maxLen - 1;
2. beg = (maxCenter - maxLen)/2
   则最长子串为s.substr((maxCenter - maxLen)/2,maxLen - 1);

接下来分析如何从新字符串中找出最长回文子串.
设新字符串为t,目前能延伸到最右端的回文子串圆心为po,延伸到最右端的位置为mx,数组p保存以t每一点为圆心的回文子串的半径,如p[i]表示以t[i]为圆心的回文子串的半径,有
p[i] = mx > i ? min(p[2 * po - i], mx - i) : 1;

1. 如果i < mx:则t[i]关于po的对称点必定在以po为圆心的最长回文子串内.对称坐标为po - (i - po) = 2* po -i,则以t[i]为中心的回文串半径为其对称点的半径或者mx - i的值
2. 如果i > mx则需要重新计算

class Solution {
public:
    string adjust(string const & str){
        size_t size = str.size();
        string strNew(size * 2 + 2,'#');
        strNew[0]= '$';
        int j = 2;
        for(size_t i = 0; i < size; ++i) {
            strNew [j] = str[i];
            j += 2;
        }
        return strNew;
    }
    string longestPalindrome(string s) {
        string strNew = adjust(s);
        size_t mx = 0; //回文串能延伸到的最右端的位置
        size_t po = 0; //能延伸到最右端的回文子串中心的位置
        
        size_t maxCenter = 0;   //最长回文子串的中心位置
        size_t maxLen = 0;      //最长回文子串的半径
        size_t size = strNew.size();
        vector<size_t> p(size);
        for(int i = 1; i < size; i++){
            p[i] = mx > i ? min(p[2*po - i],mx - i):1;
            while(strNew[i + p[i]] == strNew[i - p[i]]) {
                p[i]++;
            }
            if(i + p[i] > mx) {
                mx = i + p[i];
                po = i;
            }
            if(maxLen < p [i]){
                maxLen = p[i];
                maxCenter = i;
            }
        }
        return s.substr((maxCenter - maxLen)/2,maxLen - 1);
    }
};