题解 SP7586 【NUMOFPAL - Number of Palindromes】
顾z
2018-10-30 18:22:07
> ### Description
>
> 求一个串中包含几个回文串。
>
> ### Input
>
> 输入一个字符串$S$
>
> ### Output
>
> 包含的回文串的个数.
看到题解里面有人人写回文自动机.
有必要那么麻烦嘛 emmm
我们直接跑$Manacher$就好了啊.
答案就是以每一位为中心的回文串长度/2的和。
(如果添加字符则为回文半径长度/2。)
这个就不多解释了.很明显的一个东西。
不能理解的话,可以看下这个
> ＃ a ＃ a ＃ b ＃ a ＃ a ＃
>
> 1 2 3 2 1 6 1 2 3 2 1
>
> 数字对应于每一个位置的回文半径
>
> .(实际上减去$1$才是,但是计算的时候要加上1,所以代码里面直接用了这个.)
``代码``
```c++
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define R register
using namespace std;
const int maxn=1008;
char ch[maxn];
char s[maxn<<2];
int len,RL[maxn<<2],MaxRight,center,ans;
int main()
{
scanf("%s",ch);
len=strlen(ch);
for(R int i=0;i<len;i++)s[2*i+1]=ch[i];
len=2*len+1;
for(R int i=0;i<len;i++)
{
if(i<=MaxRight)
RL[i]=min(RL[2*center-i],MaxRight-i);
else RL[i]=1;
while(s[i-RL[i]]==s[i+RL[i]] and i-RL[i]>=0 and i+RL[i]<len)
RL[i]++;
if(i+RL[i]-1>MaxRight)
MaxRight=i+RL[i]-1,center=i;
}
for(R int i=0;i<len;i++)ans+=RL[i]/2;
printf("%d",ans);
}
```