牛客题霸--最长回文子串题解

马拉车算法求最长回文子串

class Palindrome {
public:
    int getLongestPalindrome(string A, int n) {
        string str = "@#";
        int p[100010], id = 0, mx = -1, maxn = -1;
        memset(p, 0, sizeof(p));

        for ( int i = 0; i < n; i++ ) {
            str += A[i];
            str += '#';
        }

        for ( int i = 0; i < str.size(); i++ ) {
            if ( i < mx ) p[i] = min(p[ id * 2 - i], mx - i);
            else p[i] = 1;

            while ( str[i-p[i]] == str[i + p[i]]) p[i]++;

            if ( p[i] + i > mx) {
                id = i;
                mx = p[i] + i;
            }

            maxn = max(maxn, p[i]-1);
        }
        return maxn;
    }
};