最长回文子串

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

示例

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

题解

一般方法，遍历每一个字符然后向两边扩展，时间复杂度O(n * n);马拉车算法利用动态规划的思想可以达到时间复杂度O(n).

class Solution {
public:
    string longestPalindrome(string s) {
        string manStr = ToManStr(s);
        vector<int> manVec(manStr.size(), 0);
        int m = -1;         //回文中心
        int r = -1;         //回文右边界
        int index = -1;     //最长回文子串中心
        int len = 0;        //最长回文串长度
        string result;
        for(int i = 0; i < manStr.size(); ++i) {
            manVec[i] = i < r ? min(manVec[m * 2 - i], r - i) : 1;
            while(i + manVec[i] < manStr.size() && i - manVec[i] >= 0) {
                if(manStr[i + manVec[i]] == manStr[i - manVec[i]])
                    ++manVec[i];
                else
                    break;
            }
            if(i + manVec[i] > r) {
                r = i + manVec[i];
                m = i;
            }
            if(manVec[i] > len) {
                len = manVec[i];
                index = i;
            }
        }
        len -= 1;
        for(int i = index - len; i <= index + len; ++i) {
            if(manStr[i] != '#')
                result.push_back(manStr[i]);
        }
        return result;
    }

    string ToManStr(string& str) {
        int len = str.size();
        string manStr(2 * len + 1, ' ');
        int index = 0;
        for(int i = 0; i < 2 * len + 1; ++i) 
            manStr[i] = (i % 2) == 0 ? '#' : str[index++];
        return manStr;
    }
};