A2401 [THUPC 2018] 绿绿和串串

#include <bits/stdc++.h>
using namespace std;

// z[i] = s 与 s[i..] 的最长公共前缀长度
vector<int> zFunction(const string &s) {
    int n = (int)s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

// d1[i]：以 i 为中心的奇回文半径（含中心）；d2[i]：中心在 i-1 与 i 之间的偶回文半径
void manacher(const string &s, vector<int> &d1, vector<int> &d2) {
    int n = (int)s.size();
    d1.assign(n, 0);
    d2.assign(n, 0);
    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 (i - k >= 0 && 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 (i - k - 1 >= 0 && 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;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int m = (int)s.size();

        // |S| = 1 时，R 只能是那一个字符本身
        if (m == 1) {
            cout << "1\n";
            continue;
        }

        // T = S[1..m-1]：判定周期时要用它
        string t = s.substr(1);
        int n = (int)t.size();
        vector<int> z = zFunction(t);
        vector<int> d1, d2;
        manacher(s, d1, d2);

        // S[l..r] 是否回文
        auto isPalindrome = [&](int l, int r) -> bool {
            int len = r - l + 1;
            int c = (l + r) / 2;
            if (len & 1) return d1[c] >= (len + 1) / 2;
            return d2[c + 1] >= len / 2;
        };

        bool first = true;
        // d = |R| - 1，候选长度 L = d + 1
        // （L = 1 即 d = 0 时翻转不会让串变长，只有 m = 1 才可能，故从 d = 1 开始）
        for (int d = 1; d <= m - 1; d++) {
            // 条件一：以 d 为中心的最长回文区间
            int rad = min(d, m - 1 - d);
            if (!isPalindrome(d - rad, d + rad)) continue;

            // 条件二：T = S[1..m-1] 以 2d 为周期
            if (2 * d < n && z[2 * d] < n - 2 * d) continue;

            if (!first) cout << ' ';
            first = false;
            cout << d + 1;
        }
        cout << '\n';
    }
    return 0;
}