马拉车

vector<int> manacher(string &s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}
// r[a + b + 1] 代表的就是转换后字符串中 s[a] 和 s[b] 中间的位置下标
// 若 r[a + b + 1] > b - a + 1 则 a ~ b 是回文串
// 注意严格使用下标代入a, b！！！