P5446 题解

· · 题解

一开始我只想出了判断经过一次翻转的处理，然后看到了这篇题解。

感觉大佬讲的不是很清晰，希望我能帮助各位理解。

设给出的前缀串为 s。

从题目来看就可以知道分为两种情况：

  1. 当前的串经过一次翻转得到的字符串，s 是此串的前缀；

  2. 当前的串经过多次翻转得到的字符串，s 是此串的前缀。

对于第一种情况，我们看下面这张图。

蓝红两条竖线分别为以 i 为中心的最大回文串的左右端点，可以发现，如果要是当前的串以 i 为末尾进行折叠的话，就会产生一个串，而这个串的前缀里面就有给出的 s，因为 p[i] 是在 s 串中求得的，所以如果要是 i+p[i]-1=cnt 的话，翻转过来的时候，得到的新串 a 中的 a[i] ~ a[i+p[i]-1] 一定是与 s[i] ~ s[cnt] 的部分是完全一样的，只有这种情况以 i 为末尾翻转一次是可以的，这个时候我们用 g 数组来标记一下。

对于第二种情况，不好用图来解释，我们用样例中的 qwqwq 来解释：我们从样例的输出得知，qw 是可以经过两次翻转得到一个字符串 a，s 是 a 的前缀的，而我们发现，我们可以发现 qw 翻转一次是 qwq，qwq 是可以经过一次翻转就得到 qwqwq 的！也就是说，我们可以利用之前翻转一次就可以的点来寻找需要翻转两次，三次等等才能得到目标串的！那么我们翻转一次后再翻转一次能得到答案的标志是什么？就是我们翻转后的右端点的 g 数组是被标记过的！也就是说 g[i+p[i]-2]=1，为什么下标是 i+p[i]-2 嘞？因为我们知道 manacher 算法是要插入字符的，而这时求的回文串是有插入的特殊字符的，再向左移一位才是真正的回文串的结尾的字符。这个时候还需要注意的一点就是因为我们的串要翻转多次才能达到目标串，可以看出当前的最大回文半径是 i，也就是说 i=p[i] 才行（因为要整个翻转过来嘛）。

code

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int T,n,p[N<<1],g[N<<1],cnt;
char s[N<<1];
inline void qk()
{
    for(int i=1;i<=cnt;i++)
      p[i]=g[i]=0;
}
signed main()
{
    cin>>T;
    while(T--)
    {
        cnt=0;
        char c=getchar();
        s[0]='!';s[++cnt]='%';
        while(c<'a'||c>'z')c=getchar();
        while(c>='a'&&c<='z')s[++cnt]=c,s[++cnt]='%',c=getchar();
        s[cnt+1]='#';
        qk();
        int j=0,mid=0;
        for(int i=1;i<=cnt;i++)
        {
            if(i<=j)p[i]=min(p[2*mid-i],j-i+1);
            while(s[i+p[i]]==s[i-p[i]])p[i]++;
            if(i+p[i]>j)j=p[i]+i-1,mid=i;
        }
//      for(int i=2;i<=cnt;i+=2)
//        cout<<p[i]-1<<" ";
//      cout<<endl;
        for(int i=cnt-1;i>=1;i-=2)
        {
            if(i+p[i]-1>=cnt)g[i]=1; 
            else if(g[i+p[i]-2]&&i==p[i])g[i]=1;
            else continue;
        }
        for(int i=2;i<=cnt;i+=2)
            if(g[i])cout<<i/2<<" ";
        cout<<endl;
    }
    return 0;
}