Description：

定义字符串的翻转：将前 $|R|−1 $ 个字符倒序后，插入到该串的最后。

给一个字符串，求出他的所有能过通过多次翻转使得大串变成了他的一个前缀的大串的前缀。

多次询问。

$1\leqslant\sum n\leqslant5\times10^6$

Solution：

发现如果一个前缀翻转过后原串成了他的一个前缀，那这样的位置一定是好的，如果翻转后能匹配且结尾位置是好的，那么这个位置也是好的，于是先把字符串后面加 $l-1$ 个通配符，然后用 $manacher$ 求最长回文半径，然后倒序循环，对每个位置判断回文左端点是不是 $1$ ，右端点是不是超出 $n$ 或者合法即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXL 1000010

char s[MAXL];

char c[MAXL << 1];

int h[MAXL << 1];

int p[MAXL];

int stack[MAXL],top = 0;

bool v[MAXL];

inline void print(int k)

{

	if(k / 10 > 0)print(k / 10);

	putchar(k % 10 + '0');

	return;

}

inline void work()

{

	scanf("%s",s + 1);

	register int l = strlen(s + 1);

	if(l == 1)

	{

		puts("1");

		return;

	}

	register int tot = 0;c[++tot] = '#';

	for(register int i = 1;i <= l;++i)

	{

		c[++tot] = s[i];

		c[++tot] = '#';

	}

	register int n = tot;

	register int pos = 1,maxr = 1;

	for(register int i = 1;i <= n;++i)

	{

		if(maxr >= i)h[i] = min(maxr - i + 1,h[2 * pos - i]);

		else h[i] = 1;

		while(i - h[i] >= 1 && (i + h[i] > n || c[i - h[i]] == c[i + h[i]]))++h[i];

		if(i + h[i] - 1 > maxr)

		{

			maxr = i + h[i] - 1;

			pos = i;

		}

	}

	n = l;

	for(register int i = 1;i <= n;++i)

	{

		v[i] = false;

		p[i] = h[i * 2] / 2;

	}

	top = 0; 

	for(register int i = n;i >= 1;--i)

	{

		if(i == p[i] && (i + p[i] - 1 > n || v[i + p[i] - 1]))

		{

			stack[++top] = i;

			v[i] = true;

		}

	}

	while(top != 0)

	{

		print(stack[top]);putchar(' ');

		--top;

	}

	puts("");

	return;

}

int main()

{

	freopen("string.in","r",stdin);

	freopen("string.out","w",stdout);

	register int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}