题意

定义一种操作，以最后一位为中心将字符串 $s$ 的前 $|s|-1$ 位回文。

现在给定一个字符串 $s$ ，问有多少种长度的初始字符串 $t$ ，使得 $s$ 是 $t$ 翻转若干次后的前缀。

$|s|\leq10^6$ 。

题解

由于本题一定是奇长度的回文串，所以不用在字符串中加入特殊字符。

然后跑 Manacher，如果 $R_i$ 的范围大过 $|s|$ 就可取。

代码

const int N = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	char s[N];
	int R[N];
	bool Ans[N];

	void manacher() {
		memset (R, 127 / 3, sizeof R);
		int p = 1, mx = 1;
		for (int i = 1; i <= n; i++) {
			R[i] = min(mx - i, R[2 * p - i]);
			for (; s[i - R[i]] == s[i + R[i]]; R[i]++);
			if (i + R[i] > mx)
				mx = i + R[i], p = i;
		}
	}

	int main() {
		for (int t = Read(); t--; ) {
			memset (Ans, 0, sizeof Ans);
			scanf ("%s", s + 1);
			n = strlen(s + 1);
			s[0] = '@';
			manacher();
			for (int i = n; i; i--)
				if (i + R[i] > n || Ans[i + R[i] - 1] && R[i] == i)
					Ans[i] = 1;
			for (int i = 1; i <= n; i++)
				if (Ans[i]) printf ("%d ", i);
			putchar(10);
		}
		return 0;
	}
}

int main () {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	Main::main();
	return 0;
}