Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

用的 Manacher 算法，如果对注释不太明白可以搜网上的图解。。


class Solution
{

public:
    string longestPalindrome(string s)
    {
        // 马拉车算法
        if (s.empty())
            return "";

        // 先处理一下字符串，给每个字符之间加入#，来解决对称位置的奇偶问题
        // 保证所有的串和回文串都是奇数长度    
        string prep = "#";
        for (auto ch : s)
        {
            prep += ch;
            prep += "#";
        }

        const int size_p = prep.size();
        // dp(i) 表示以 i 为中心的最长回文的半径
        vector<int> dp(size_p, 0);
    
        // bCur 是以 center 为中心，最长回文的右边界
        int center = 0, bCur = 0;
        for (int i = 0; i < size_p; i++)
        {
            // 遍历是从左至右，所以
            // center一定小于等于i
            // 到i的时候，dp[mirror]是最长回文半径
            // mirror 是以 center 为中心，i的对称点
            int mirror = center - (i - center);

            // 这里分三种情况：
            // 1. dp[mirror] > bCur - i,那么 dp[i] = bCur - i，否则的话以 center 为中心，到 bCur 的长度就不是最长回文半径了，与假设不符
            // 2. dp[mirror] < bCur - i,那么 dp[i] = dp[mirror],根据 i 和 mirror 是以 center 为中心对称，且 dp[mirror] 在 center 为中心的回文之内，如果 dp[i] 比 dp[mirror] 更大的话，那么与 dp[mirror] 是最大回文前置条件不符
            // 3. dp[mirror] == bCur - i，那么 i 的最长回文至少是包含 mirror 的，即 dp[i] >= dp[mirror]，所以还需要后面继续扩展 i 的回文长度的处理。
            dp[i] = bCur <= i ? 0 : min(bCur - i, dp[mirror]);

            // 继续扩展 i 的回文长度，只有第三种情况的时候才有效，前两种情况必不满足 prep[start - 1] == prep[end + 1]
            int start = i - dp[i], end = i + dp[i];
            while (start - 1 >= 0 && end + 1 < size_p && prep[start - 1] == prep[end + 1])
            {
                --start;
                ++end;
                ++dp[i];
            }

            // 更新 center 和 bCur
            if (i + dp[i] > bCur)
            {
                bCur = i + dp[i];
                center = i;
            }
        }
        center = max_element(dp.begin(), dp.end()) - dp.begin();
        return s.substr((center - dp[center]) / 2, dp[center]);
    }
};