根据题目能发现一个性质，设转化前的字符串为 \(s\)，转化后的字符串为 \(s'\)，则 \(s'_{|s|}\) 为 \(s'\) 的中心，即 \(s'_{|s|}\) 求出来的回文串左边界为 \(1\) 右边界为 \(|s'|\)
找出这个性质就挺简单了，考虑先对给出的 \(S\) 用 \(\text{manacher}\) 求出每个节点 \(i\) 对应的左边界 \(l_i\) 右边界 \(r_i\)，然后对于原串 \(R\) 分两种情况讨论：
- \(\text{lhzawa}\to \text{lhzawawa}\)，即 \(R\) 翻转过来但是有部分后缀被删了，此时对应在 \(S\) 中对应的 \(r_{|R|} = |S|\)，因为至少还在的部分是回文的。
需注意这种情况只会在最后一次变换为 \(S\) 时出现，前面的变换出来的结果肯定是完整串（或前面没有进行变换）。 - \(\text{lhzawa}\to \text{lhzawawazhl}\)，即 \(R\) 翻转为 \(S\) 后是完整的，此时因为 \(R\) 一定为前缀所以 \(l_{|R|} = 1\) 且 \(r_{|R|}\) 对应的也是一个可以字符串翻转为 \(S\) 的字符串 \(R'\)，这样才能保证经过后面的翻转能变为 \(S\)。
所以这个题基本上就搞定啦，步骤顺序从后往前，先特殊判断 1 情况，再由每一个之前得到的点按照 2 情况继续往前推。
因为能发现假设现在一个合法的点 \(u\)，则其可以推到的点为 \(\lceil\frac{u}{2}\rceil\)，因为 \(S_{1\sim u}\) 若能继续分下去且合法则定为一个奇回文串，找到中点即可。
于是就实现了一个类似 \(\text{BFS}\) 的过程，时间复杂度 \(\mathcal{O}(\sum|s|)\)。
需要注意的点：多测清空。
// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int len[N];
int cu[N];
int main() {
function<void ()> solve = []() -> void {
scanf("%s", s + 1);
int n = strlen(s + 1);
s[0] = '&', s[n + 1] = '$';
int mid = 0, mx = 0;
for (int i = 1; i <= n; i++) {
if (i < mx) {
len[i] = min(len[mid * 2 - i], mx - i);
}
else {
len[i] = 0;
}
for (; s[i - len[i]] == s[i + len[i]]; len[i]++);
if (i + len[i] > mx) {
mx = i + len[i], mid = i;
}
}
for (int i = 1; i <= n; i++) {
cu[i] = 0;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
len[i]--;
}
// for (int i = 1; i <= n; i++) {
// printf("%d ", len[i]);
// }
// printf("\n");
for (int i = n; i >= 1; i--) {
if (i + len[i] == n) {
q.push(i);
}
}
for (; ! q.empty(); ) {
int u = q.front();
q.pop();
cu[u] = 1;
if (u & 1) {
int v = (u >> 1) + 1;
if (! cu[v] && v + len[v] >= u && len[v]) {
q.push(v);
}
}
}
for (int i = 1; i <= n; i++) {
if (cu[i]) {
printf("%d ", i);
}
}
printf("\n");
};
int Tcs;
scanf("%d", &Tcs);
for (; Tcs; Tcs--) {
solve();
}
return 0;
}