题解 | #最长回文子串#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        // Manacher 算法
        string t = "$#"; // 初始化新字符串，添加特殊字符避免边界检查
        for (char c : A) {
            t += c;
            t += '#';
        }
        t += '@'; // 结尾添加特殊字符

        int n = t.length();
        vector<int> p(n, 0);
        int c = 0, r = 0; // 当前回文串中心和右边界
        int maxLen = 0;

        for (int i = 1; i < n - 1; ++i) {
            p[i] = (r > i) ? min(r - i, p[2 * c - 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];
            }
            maxLen = max(maxLen, p[i]);
        }

        return maxLen;
    }
};