方法一

中心扩展法

class Solution {
public:
    string longestPalindrome(string s) {
        int st = 0, ed = 0;
        for (int i = 0; i < s.size(); i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int max1 = max(len1, len2);
            if (max1 > ed - st + 1) {
                st = i - (max1 - 1) / 2;
                ed = i + max1 / 2;
            }
        }

        return s.substr(st, ed - st + 1);
    }

    int expand(string &s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }
        return r - l - 1;
    }
};

方法二

Manacher算法

class Solution {
public:
    string longestPalindrome(string s) {
        string tmp = "#";
        for (auto i : s) {
            tmp += i, tmp += "#";
        }
        s = tmp;
        int n = s.size();
        vector<int> p(n + 1);
        int st = 0, ed = 0, cen = -1, r = -1;
        for (int i = 0; i < n; i++) {
            int curlen = 0;
            if (r >= i) {
                curlen = min(r - i, p[2 * cen - i]);
                curlen = expand(s, i - curlen, i + curlen);
            } else {
                curlen = expand(s, i, i);
            }
            p.push_back(curlen);
            if (i + curlen > r) {
                r = i + curlen;
                cen = i;
            } 
            if (2 * curlen + 1 > ed - st + 1) {
                st = i - curlen;
                ed = i + curlen;
            }
        }
        string ans = "";
        for (int i = st; i <= ed; i++) {
            if (s[i] != '#') ans += s[i];
        } 

        return ans;
    }

    int expand(string &s, int l, int r) {
        while (l >= 0 && r < s.length() && s[l] == s[r]) l--, r++;

        return (r - l - 1) / 2;
    }
};
最后修改:2021 年 03 月 30 日 12 : 50 PM