LeetCode----最长回文子串「动态规划」

题目

题目描述

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

示例

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

分析

　　暴力法：直接从头到尾一次遍历，通过中心扩展往两边找最长子串即可。

　　马拉车算法（Manacher）：使用Manacher算法，动态规划的找到最长回文子串

图解

　　施工中。。。

代码

string longestPalindrome(string s) {
        int len = s.length();
        string ma = "#";
        for(int i = 0; i < len; ++i) {
            ma.push_back(s[i]);
            ma.push_back('#');
        }
        int mx = 0, id = 0, new_len = len*2+1, p = 0, mp[new_len];
        for(int i = 0; i < new_len; ++i) {
            mp[i] = mx > i ? min(mp[2*id-i], mx-i) : 1;
            while(i-mp[i] >= 0 && ma[i-mp[i]] == ma[i+mp[i]]) ++mp[i];
            if(i+mp[i] > mx) {
                mx = i + mp[i];
                id = i;
            }
            if(mp[i] > mp[p]) p = i;
        }
        len = mp[p] - 1;
        p = p/2 - len/2;
        return s.substr(p, len);
    }