「Manacher」[THUPC2018] 绿绿和串串 Solution

题目链接

设每一位上的最大回文半径为f[i]（包括第i位，比如aba的b的最大回文半径为2），n为字符串长度，视字符串第一位下标为1（虽然我写的是从0开始）。

满足题意有的位置有两种情况（画画图比较容易理解）：

• 对于第i位，若i+f[i]-1==n则这一位一定是满足题目条件的。相当于这时当前串一定是第i位左侧翻转拼接后形成的字符串的前缀。
• 若i-f[i]==1且第i+f[i]-1位是可行解，则当前位一定能经过若干次翻转拼接形成满足题意的原串。

最大回文半径用Manacher求。

#include <bits/stdc++.h>
using namespace std;
namespace IO{
    #define I inline
    I char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
    I void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}
//    I void read(int &x){scanf("%d",&x);}
    #undef I
}using namespace IO;
class Manacher{
    private:
        string S,P;
        int Mx,j,MaxR;
        void init(void){//下标从0开始
            char c;
            S=P="";
            len=Mx=j=MaxR=0;
            while((c=tc())>='a'&&c<='z'){
                ++len,S+=c;
            }
        }
        #define max(x,y) ((x)>(y)?(x):(y))
        void GetFn(){
            init(),j=0;
            P+="&#";for(int i=0;i<S.size();i++)P+=S[i],P+='#';P+='~';
            for(int i=1;i<P.size()-1;i++){
                f[i]=Mx>i?min(Mx-i,f[(j<<1)-i]):1;
                while(P[i+f[i]]==P[i-f[i]]&&i+f[i]<P.size())f[i]++;
                if(i+f[i]>Mx)Mx=i+f[i],j=i;
                MaxR=max(MaxR,f[i]);
            }
        }
        #undef max
    public:
        #define N 1000005
        int len,f[N<<1];
        #undef N
        void Solve(void){GetFn();}
        int GetF(int x){return f[x+1<<1]>>1;}//下标从0开始的最大半径(有中心点字符)，无中心点字符需要自行枚举。
        int GetMaxR(void){return MaxR-1;}//返回最大半径
}S;
#define N 1000005
int T,Cnt,vis[N];
int main()
{
    for(read(T);T;--T){
        ++Cnt,S.Solve();
        for(int i=S.len-1;~i;--i){
            if(i+S.GetF(i)==S.len)vis[i]=Cnt;
            else if(i+1-S.GetF(i)==0&&vis[i+S.GetF(i)-1]==Cnt)vis[i]=Cnt;
        }
        for(int i=0;i<S.len;++i)if(vis[i]==Cnt)printf("%d ",i+1);
        puts("");
    }
}