Manacher|马拉车算法|回文子串

// 马拉车算法，O(n)时间处理字符串所有子串的回文问题
// https://oi-wiki.org/string/manacher/
// 例题：https://leetcode.cn/problems/check-if-dfs-strings-are-palindromes/description/
// https://leetcode.cn/problems/longest-palindromic-substring/description/
class Manacher {
    vector<int> d1; // 奇数长度子串的半径，d1[i] = r 表示，以下标i为中心的最长回文子串半径是r（长度是2r-1）
    vector<int> d2; // 偶数长度子串的半径，d2[i] = r 表示，以下标i为右中心的最长回文子串半径是r（长度是2r）
public:
    Manacher(const string& s) {
        int n = s.size();
        d1.resize(n);
        d2.resize(n);
        
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
            while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
                k++;
            }
            d1[i] = k--;
            if (i + k > r) {
                l = i - k;
                r = i + k;
            }
        }


        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
            while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
                k++;
            }
            d2[i] = k--;
            if (i + k > r) {
                l = i - k - 1;
                r = i + k;
            }
        }
    }

    // 返回s[b:e]是否回文
    bool isPalindrome(int b, int e) {
        if((e-b)%2) { // 奇数长度的子串
            int c = b + (e-b) / 2;
            int r = c - b + 1;
            return d1[c] >= r;
        } else { // 偶数长度的子串
            int c = b + (e-b) / 2;
            int r = c - b;
            return d2[c] >= r;
        }
    }

    // 返回s的最长回文子串的begin、end
    pair<int, int> longestPalindrome() {
        int b=0, e=0;
        for(int c=0;c<d1.size();c++) {
            if(d1[c]*2-1>e-b) {
                b = c+1-d1[c];
                e = c + d1[c];
            }
            if(d2[c]*2>e-b) {
                b = c - d2[c];
                e = c + d2[c];
            }
        }
        return {b, e};
    }
};