绿绿の串串题解
SpeMars
·
·
题解
这道题其实只要学会马拉车算法( manacher )就 ok 了
如果你还没有了解马拉车算法这边建议你先去别的博客学习一下
luogu模板题
个人觉得很不错的一篇manacher算法详解博客
好，那么进入正题
本题要求一个串 R 使得它的前缀为 S ，串 R 可以进行任意次翻折
但是翻折点不会重叠
eg: R = "ab" 翻折一次后 R = "aba" 而非 R = "abba"
那么我们枚举每个点i的最大回文半径
情况一:
如果当前位置回文后正好到S串的末尾，则这是可行的
注:|S|为字符串S的长度
eg: S = "abcdcb", i = 4
r[4]$ = $2$ 且 $i$ + $r[4]$= $|S|
所以我们直接把 i 当做 R 翻折后的回文中心就可以了
对于例子来讲即:
$R_1$ = "abcdcba"
情况二:
如果 $i$ 位置回文后的位置可以为 $R$ 的回文中心且回文半径刚好延伸到 $S$ 的开头，
则可以在当前位置翻折到达$R$的回文中心再进行下一次翻折
eg:$S$ = "acbcac", $i$ = $3
显然当 i = 5时符合情况一
且 r[3] = 2, 3 + r[3] = 5
正好够到 S 的开头且够到 R 的可行回文中心
$R_1$ = "acbca"
$R_2$ = "acbcacbca"
CODE:
```cpp
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int N=2e7+10;
int t;
bool ans[N];
string S;
char s[N];
int r[N];
int manacher(string str){
int len=str.size()*2+1;
memset(ans,false,sizeof(ans));
memset(r,0,sizeof(r));
str=' '+str;
int id=0,C=0,R=0,maxd=-1;
for(int i=1;i<=len;++i)s[i]=(i&1)?'*':str[++id];
for(int i=1;i<=len;++i){
r[i]=i<R?min(R-i,r[2*C-i]):1;
for(;i+r[i]<=len&&i-r[i]>=1;){
if(s[i+r[i]]==s[i-r[i]])++r[i];
else break;
}
if(i+r[i]>R){
R=i+r[i];
C=i;
}
maxd=max(maxd,r[i]);
}
return len;
}
int main(){
scanf("%d",&t);
for(;t--;){
cin>>S;
int len=manacher(S),lens=S.size();
for(int i=lens;i>=1;--i){
int ri=r[i*2];
if(ri>1){//如果原串的最大回文子串长度(不包括自己)>0
ri/=2,--ri;//计算这个回文中心在原串里的真正回文半径(不含本身)
//如果把当前位置回文正好到S串的最左端,那么这个点就是R串的回文中心
if(i+ri==lens)ans[i]=true;
//如果当前位置回文后的位置可以为R的回文中心且回文半径刚好延伸到S串的开头，则可以在当前位置翻折到达R点再进行下一次翻折
if(ans[i+ri]&&i-ri==1)ans[i]=true;
}
}
for(int i=1;i<=lens;++i)if(ans[i])printf("%d ",i);
puts("");
}
return 0;
}
/*
4
abcdcb
qwqwq
qaqaqqq
carnation
*/
```