以下是代码

#include <iostream>
#include <vector>
#include <string>
#define err '~'
#define int long long
using namespace std;

const int MAXN = 20e6 + 7;
char a[MAXN];
int dp[MAXN], can[MAXN], cnt;

void go_work(string inp)
{
	int n = inp.size();
	a[0] = err;
	for (int i = 1; i <= n; i++) a[i] = inp[i - 1]; // a[i] is overwritten, dp[i] and can[i] must change index
	for (int i = 1, mid = 0, maxr = 0; i <= n; i++)
	{
		if (i <= maxr) dp[cnt + i] = min(dp[cnt + 2 * mid - i], maxr - i + 1);
		while (a[i - dp[cnt + i]] == a[i + dp[cnt + i]]) dp[cnt + i]++;
		if (i + dp[cnt + i] - 1 >= maxr) maxr = i + dp[cnt + i] - 1, mid = i;
	}
	can[n] = true; // can[i] is the answer
	for (int i = n; i >= 1; i--)
	{
		if (i + dp[cnt + i] - 1 == n) can[cnt + i] = true;
		else if (i == dp[cnt + i]) can[cnt + i] = can[cnt + i + dp[cnt + i] - 1];
		else can[cnt + i] = false;
	}
	for (int i = 1; i <= n; i++) if (can[cnt + i]) cout << i << ' ';
	cout << endl;
	cnt += n; // Index shifting, doesn't need memset() every time
}

signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string inp; cin >> inp;
		go_work(inp); // Go Work!!!!
	}
}

据说要用 2 倍数组，中间加特殊字符，我没加。我不理解，题目不是求的是奇数长度回文数吗？