绿绿和串串(Lvlvl and Skewers) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve() {
    string s;
    if (!(cin >> s)) return;
    int n = (int)s.size();
    vector<int> d1(n, 0);
    int l = 0, r = -1;
    for (int i = 0; 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;
        }
    }
    vector<char> ok(n, 0);
    for (int i = n - 1; i >= 0; --i) {
        int rad = d1[i];
        if (i + rad - 1 == n - 1) {
            ok[i] = 1;
        } else if (i - rad + 1 == 0 && ok[i + rad - 1]) {
            ok[i] = 1;
        }
    }
    bool first = true;
    for (int i = 0; i < n; ++i) {
        if (ok[i]) {
            if (!first) cout << ' ';
            first = false;
            cout << (i + 1);
        }
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) solve();
    return 0;
}