Manacher【SP7586】NUMOFPAL - Number of Palindromes

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,所以代码里面直接用了这个.)

代码

#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);

}

巴特西

Manacher【SP7586】NUMOFPAL - Number of Palindromes

Description

Input

Output

最新文章

热门文章