Description
给定一个串 \(S\) ，要求串 \(S\) 是串 \(R\) 经过多次翻转后的前缀。问有多少种初始长度的串 \(R\) 。
串 \(R\) 翻转的定义是将前 \(|R|-1\) 个字符倒序排列后，插入到串的最后。如 \(\mathrm{aaa}\) 翻转后得到 \(\mathrm{abcdcba}\) 。
Solution
我们先设以 \(i\) 为中点的最长回文半径为 \(d_i\)(不包括自身) , 这个我们可以用 manacher 求解。
分类讨论一下：
-
如果说 \(i+d_i = |S|\) , 那么就说明我们如果以 \(i\) 为中点进行翻转，一次翻转就能行了。
比如 \(\mathrm{abcbcb}\) ，我们以第二个 \(b\) 为中点，因为通过上面的条件我们能保证翻转过后 \(i+1 - |S|\) 肯定和前面的部分相等，因此这是一种条件；
-
如果说一次翻转不能行，那我们退而求其次。如果以 \(i\) 为中点翻折后能到达另一个可行的翻折中点，并且 \(i-d_i = 1\) ， 因为要从起点开始翻折，所以我们要保证从起点开始就是回文串，也就是 \(i-d_i = 1\)。
时间复杂度 \(O(T|S|)\) ，可以通过。
最后，别忘了多测清空和边界！
Code
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e7 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
char a[N<<1],ch[N<<1];
int d[N<<1],ans[N<<1];
int T,n,cnt;
int l,r=1,di;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void Main()
{
memset(d , 0 , sizeof d);
memset(ans , 0 , sizeof ans);
cnt = 0 , l = 0 , r = 1;
cin >> (a+1);
ch[0] = '$' , ch[++cnt] = '#';
n = strlen(a+1);
for(re int i=1;i<=n;i++) ch[++cnt] = a[i] , ch[++cnt] = '#';
d[1] = 1;
for(re int i=2;i<=cnt;i++)
{
if(i <= r) d[i] = min(d[r-i+l],r-i+1);
while(ch[i-d[i]] == ch[i+d[i]] && i+d[i]<=cnt) d[i]++;
if(i+d[i]-1 > r) l = i-d[i]+1 , r = i+d[i]-1;
}
for(re int i=n;i>=1;i--)
{
di = d[i*2] / 2 - 1;//求出不含特殊字符的真正di
if(i + di == n) ans[i]=1;//情况1
if(ans[i+di] && i-di == 1) ans[i]=1;//情况2
}
for(re int i=1;i<=n;i++) if(ans[i]) cout << i << " ";
cout << "\n";
}
signed main()
{
T = read();
while(T--) Main();
return 0;
}