5. 最长回文子串

题目链接

解题思路：最长回文子串问题，首先要将原字符串扩充，比如abba，暴力是以每个字符s[i]，左右两边扩，如果是abba，得不到最优解，扩充成#a#b#b#a#，就不会有问题，最优解是manacher算法。

• 假设s[i]扩充的区域是[x, y]，是目前便利到的，最远的距离，我们称i为回文中心C，y为回文最远右边界R，同时，还用数组记录每个点，扩充的回文半径dp[i]，关系是x == i - dp[i] + 1, y == i + dp[i] - 1
• 具体的步骤见代码中的注释

代码

class Solution {
public:
    void addChar(const string &s, string &new_str) {
        for (int i = 0; i < s.size(); ++i) {
            new_str.push_back('#');
            new_str.push_back(s[i]);
        }
        new_str.push_back('#');
    }
    string longestPalindrome(string s) {
        string str = "";
        addChar(s, str);
        int C = 0;
        int R = 0;
        int n = str.size();
        vector<int> dp(n, 0);
        dp[0] = 1;
        int ans = 0;
        int ans_index = -1;
        for (int i = 1; i < n; ++i) {
            if (i > R) {
                int l = i - 1;
                int r = i + 1;
                while(l >= 0 && r < n) {
                    if (str[l] == str[r]) {
                        l--;
                        r++;
                    } else {
                        break;
                    }
                }
                if (r - 1 > R) {
                    R = r - 1;
                    C = i;
                }
                dp[i] = r - i;
                if (dp[i] > ans) {
                    ans = dp[i];
                    ans_index = i;
                }
                
            } else {    // i 在R内   找到i的对称点
                int i1 = 2 * C - i;
                int L = 2 * C - R;
                if (i1 - dp[i1] + 1 > L) {    // 彻底在内
                    dp[i] = dp[i1];
                } else if(i1 - dp[i1] + 1 == L) {   // 扩
                    int r = R + 1;
                    int l = 2 * i - r;
                    while(l >= 0 && r < n) {
                        if (str[l] == str[r]) {
                            r++;
                            l--;
                        } else {
                            break;
                        }
                    }
                    dp[i] = r - i;
                    if (r - 1 > R) {
                        R = r - 1;
                        C = i;
                    }
                    if (dp[i] > ans) {
                        ans = dp[i];
                        ans_index = i;
                    }
                } else {
                    dp[i] = R - i + 1;
                }
            }
        }
        string ans_str = "";
        for (int i = ans_index - ans + 1; i <= ans_index + ans - 1; i++){
            if (str[i] != '#') {
                ans_str.push_back(str[i]);
            }
        }
        return ans_str;
    }
};