题解 | #最长回文子串#

马拉车算法

注释已经写下大致思路

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string s) {
        // write code here
        int n = s.size();
        vector<int> d1(n, 0), d2(n, 0);
        int a1 = 0, a2 = 0;
        // 考虑以i为中心，半径为d1[i]的奇数长度回文串
        for(int i = 0, l = 0, r = -1; i < n; i++)
        {
            // 当i<=r, 即i在已确认的“外部”回文串s[l..r]时，
            // 显然[l..r]有一个与i对称的j = l + r - i, 显然j < i
            // 如果以j为中心的回文串的左边界大于等于l，则d1[i]显然等于d1[i]
            // 即使使用暴力扩展, 也不可能出现回文串长度增大的情况
            // 如果以j为中心的回文串的左边界小于l
            // 那么可确定的以i为中心的字符串半径是r - i + 1, 可能会更大
            // 因而需要使用暴力去扩展i为中心的字符串
            int k = (i > r ? 1 : min(d1[l + r - i], r - i + 1));
            while(i >= k && i + k < n && s[i - k] == s[i + k]){
                k++;
            }
            d1[i] = k--;
            a1 = max(a1, d1[i]);
            // 始终需要维护右边界最靠右的回文串
            if(i + k > r)
            {
                r = i + k;
                l = i - k;
            }
        }
        // 偶数长度回文串类似
        for(int i = 0, l = 0, r = -1; i < n; i++){
			// 一个比较绕的地方在于，偶数长度回文串取(l + r) / 2 + 1作为回文中心
			// 因而，j = l + r - i虽然在[l..r]与i对称，但以j为回文中心的串和以i为回文中心的串并不对称
		  	// 作为回文中心，i与j + 1才是对应的
            int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1));
            while(i >= k + 1 && i + k < n && s[i - k - 1] == s[i + k]){
                k++;
            } 
            d2[i] = k--;
            a2 = max(a2, d2[i]);
            if(i + k > r)
            {
                r = i + k;
                l = i - k - 1;
            }
        }
        return max(2 * a1 - 1, 2 * a2);
    }
};