题解 | #最长回文子串#

经典马拉车算法，马拉车算法的原理就是利用回文串的镜像对称省去了不必要的比较

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int len = 2 * n + 1;
        string b(len,'#');
        if (n < 2) {
            return n;
        }
        for (int i = 0; i < n; i++) {
            b[2 * i + 1] = A[i];
        }
        vector<int>p(2 * n + 1, 0);
        int maxlen = 1;
        int maxRight = 0;
        int center = 0;
        for (int i = 0; i < len; i++) {
            if (i < maxRight) {
                int mirror = 2 * center - i;
                p[i] = min(maxRight - i, p[mirror]);
            }
            int left = i - (1 + p[i]);
            int right = i + (1 + p[i]);
            while (left >= 0&&right<len&&b[right]==b[left])
            {
                p[i]++;
                left--;
                right++;
            }
            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                center = i;
            }
            if (p[i] > maxlen)
                maxlen = p[i];
        }
        return maxlen;
    }
};
static const auto io_sync_off=[]()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();