题解 P1210 【回文检测】
顾z
2018-09-06 16:56:31
题目描述--->[P1210 回文检测](https://www.luogu.org/problemnew/show/P1210)
## 广告： [安利blog](https://www.luogu.org/blog/RPdreamer/#)
## 分析:
看到回文显然想到了**manacher算法**(**线性求解**回文串问题
如果不了解还是去敲一下板子,学习一下比较好.-->[manacher](https://www.luogu.org/problemnew/show/P3805)
题目要求我们求出只包含字母的回文串的长度.
如果你会manacher,这很简单.
只需要**在输入之后处理一下我们得到的串**即可.
**这题的难点在于,如何输出原串**
---
**吐槽**
本来以为求出我们的最长回文半径的最中间的位置的字符,判断其左右两侧遇到的第一个字符是否相等,如果相等我们就可以一直扩展过去,直至无法匹配.
感觉这种被卡的概率还是很低的...
兴冲冲地码了100多行.然而还是被卡了,绝望地很.
---
## 解决
**首先明确：**
s数组为我们的原字符数组.
str数组为我们只含有大写(小写)字母的字符数组
ss数组为我们用于跑manacher的字符数组
**因此考虑去记录字符在原数组中的位置.**
很容易将我们转化后的数组记录.
这样记录↓
```cpp
for(RI i=0;i<l;i++)//l为我们原串长度,从l=0开始记录.
{
if((s[i]>='a' and s[i]<='z') or (s[i]>='A' and s[i]<='Z'))
str[len]=s[i],pos[len]=i,len++;
//我们只存储为字母的情况.
}
```
**处理**我们得到的数组↓
```cpp
for(RI i=0;i<len;i++)
{
if(str[i]>='a' and str[i]<='z')
str[i]-=32;
}//在这里将小写转为大写.
//也可以将大写转为小写
//视个人爱好而定.
```
此时我们已经记录了某一位置对应的原串位置.
接下来就是我们的manacher操作了!
**处理**我们用于manacher的数组↓
```cpp
for(RI i=0;i<len;i++)ss[2*i+1]=str[i];
ll=2*len+1;//这里记得变换长度.
//这里我并没有进行插入字符的操作
//是因为我们的字符数组默认为空.
//这样的处理操作会使得中间空出一些位置.从而达到插入字符的效果.
```
我们现在需要考虑的是**如何对我们用于manacher操作的数组进行标记操作**,即对应原串位置.
因为我们用于manacher的数组ss[2*i+1]对应str[i],
所以我们的数组poss[2*i+1]也会对应pos[i].
所以我们的答案就很明显了.
最左端位置就是le=i-(RL[i]-1)+1
最右端位置就是ri=i+(RL[i]-1)-1
其中RL[i]-1代表以i为对称轴的回文子串长度
所以我们**枚举poss[le]到poss[ri]输出答案**即可.
--------------------代码--------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
char s[200008],str[200008],ss[400008];
int l,len,pos[200008],RL[200008],ll,ans,le,ri,poss[200008];
int main()
{
while(~(s[l]=getchar())){l++;}//输入还是看了其他人的 emmmm,自己写的一个炸了 emmm
for(RI i=0;i<l;i++)
{
if((s[i]>='a' and s[i]<='z') or (s[i]>='A' and s[i]<='Z'))
str[len]=s[i],pos[len]=i,len++;
}
for(RI i=0;i<len;i++)
{
if(str[i]>='a' and str[i]<='z')
str[i]-=32;
}
int MaxRight=0,center=0;RL[0]=1;
for(RI i=0;i<len;i++)ss[2*i+1]=str[i],poss[2*i+1]=pos[i];//这里的对应操作.
ll=2*len+1;
for(RI i=1;i<ll;i++)
{
if(i<=MaxRight)
RL[i]=std::min(RL[2*center-i],MaxRight-i);
else RL[i]=1;
while(i-RL[i]>=0 and i+RL[i]<ll and ss[i+RL[i]]==ss[i-RL[i]])
RL[i]++;
if(i+RL[i]-1>MaxRight)MaxRight=i+RL[i]-1,center=i;
if(RL[i]-1>ans)
{
ans=RL[i]-1;
le=i-RL[i]+2;
ri=i+RL[i]-2;
}
}
printf("%d\n",ans);
for(RI i=poss[le];i<=poss[ri];i++)std::cout<<s[i];
}
```