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

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"

AC代码

string odd(string s, int idx) {
    int t = 0;
    for (int j = 0; idx - j >= 0 && idx + j < s.size(); ++j) {
        if (s[idx - j] == s[idx + j]) t++;
        else break;
    }
    string res = s.substr(idx - t + 1, 2 * t - 1);
    return res;
}

string even(string s, int idx) {
    int t = 0;
    string res;
    if (s.size() == 1) return s;
    if (idx + 1 < s.size() && s[idx] == s[idx + 1]) {
        for (int j = 0; idx - j >= 0 && idx + j + 1 < s.size(); ++j) {
            if (s[idx - j] == s[idx + 1 + j]) t++;
            else break;
        }
        res = s.substr(idx - t + 1, 2 * t);
    }
    else
        res = s.substr(idx, 1);
    return res;
}

class Solution {
public:
    string longestPalindrome(string s) {
        string ans, s_odd, s_even;
        for (int i = 0; i < s.size(); ++i) {
            s_odd = odd(s, i);
            s_even = even(s, i);
            if (s_odd.size() > s_even.size() && s_odd.size() > ans.size())
                ans = s_odd;
            else if (s_even.size() >= s_odd.size() &&
                     s_even.size() > ans.size())
                ans = s_even;
        }
        return ans;
    }
};

马拉车算法

string pre(string s) {
    string str("^");
    for (int i = 0; i < s.size(); ++i) {
        str.push_back('#');
        str.push_back(s[i]);
    }
    str.push_back('#');
    str.push_back('@');
    return str;
}

class Solution {
public:
    string longestPalindrome(string s) {
        string T = pre(s);
        vector<int> P(T.size());
        int C = 0, maxLen = 0, R = 0, idx = 0;
        for (int i = 1; i < T.size() - 1; ++i) {
            int i_mirror = 2 * C - i;
            if (R > i)
                P[i] = min(R - i, P[i_mirror]);
            else
                P[i] = 0;
            while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) P[i]++;
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
            if (P[i] > maxLen) {
                maxLen = P[i];
                idx = i;
            }
        }
        int start = (idx - maxLen) / 2;
        string ans = s.substr(start, maxLen);
        return ans;
    }
};

总结

1、最暴力的O(n³)复杂度不考虑，选择了O(n²)复杂度从中间向两边拓展的方法，要分奇偶，且细节比较多，各种加一减一的调试了很久
2、学习了Manacher算法，参考http://windliang.cc/2018/08/05/leetCode-5-Longest-Palindromic-Substring/