Luogu

LOJ

分析

这个“翻转”操作很容易想到回文。

考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一：

• 回文半径右侧达到 $|S|$ 。
• 回文半径左侧达到 $1$ ，且右端点合法。

那么只需要用 manacher 求出回文半径，然后从后往前判断就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

int n,f[N],ok[N];
char a[N],s[N];

inline void manacher(int n) {
    fill(f,f+n+2,0),fill(ok,ok+n+2,0);
    for (re int i=1,mid,mr=1;i<=n;++i) {
        f[i]=i<mr?min(f[(mid<<1)-i],f[mid]+mid-i):1;
        while (s[i+f[i]]==s[i-f[i]]) ++f[i];
        if (i+f[i]>mr) mr=i+f[i],mid=i;
    }
    for (re int i=n;i;--i)
        ok[i]=(i+f[i]-1==n)|(i-f[i]+1==1&&ok[i+f[i]-2]);
}

int main() { int T=read();
    while (T--) {
        scanf("%s",a+1); n=strlen(a+1);
        s[0]='~',s[1]='`';
        for (re int i=1;i<=n;++i) s[i<<1]=a[i],s[i<<1|1]='`';
        s[(n<<1)+2]='\0'; manacher((n<<1)+1);
        for (re int i=1;i<=n;++i) if (ok[i<<1]) printf("%d ",i);
        puts("");
    }
    return 0;
}