欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LOJ#6387. 「THUPC2018」绿绿与串串 / String【manacher】

程序员文章站 2024-03-17 16:57:10
...

传送门

解题思路:

签到题。先manacher,一个点如果回文右端点抵到n则合法,或是左端点抵到1且右端点合法。

#include<bits/stdc++.h>
using namespace std;
int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}
const int N=2000005;
int n,m,r[N],ans[N];char s[N],t[N];
void solve()
{
    scanf("%s",s+1);n=strlen(s+1);
    t[m=0]='!',t[++m]='#';
    for(int i=1;i<=n;i++)ans[i]=0,t[++m]=s[i],t[++m]='#';
    t[++m]='?',ans[n+1]=0;
    int mx=0,po=0;
    for(int i=1;i<=m;i++)
    {
        if(mx>i)r[i]=min(r[2*po-i],mx-i);
        else r[i]=1;
        while(t[i-r[i]]==t[i+r[i]])r[i]++;
        if(i+r[i]>mx)po=i,mx=i+r[i];
    }
    for(int i=1;i<=m;i++)r[i]--;
    for(int i=n;i;i--)
    {
        int R=r[i*2];
        if(!(R&1))continue;
        R>>=1;
        if(i+R==n)ans[i]=1;
        if(i-R==1&&ans[i+R])ans[i]=1;
    }
    for(int i=1;i<=n;i++)if(ans[i])cout<<i<<' ';
    cout<<'\n';
}
int main()
{
    //freopen("lx.in","r",stdin);
    for(int T=getint();T;T--)solve();
}