【HIHOCODER 1589】回文子串的数量（Manacher）

描述

给定一个字符串S，请统计S的所有|S| * (|S| + 1) / 2个子串中(首尾位置不同就算作不同的子串)，有多少个是回文字符串？

输入

一个只包含小写字母的字符串S。

对于30%的数据，S长度不超过100。

对于60%的数据，S长度不超过1000。

对于100%的数据，S长度不超过800000。

输出

回文子串的数量

样例输入

abbab

样例输出

题解

利用Manacher，可以得到每个回文中心和其半径，不用去重，直接统计就好

#include <bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define PI acos(-1)

#define bug puts("here")

#define REP(i,x,n) for(int i=x;i<=n;i++)

#define DEP(i,n,x) for(int i=n;i>=x;i--)

#define mem(a,x) memset(a,x,sizeof(a))

using namespace std;

inline int read(){

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int N=800000+10;

char s[N],str[N*4];

int p[N*4],len1,len2;

void init(){

    len1=strlen(s);

    str[0]='(';

    str[1]='#';

    for(int i=0;i<len1;i++){

        str[i*2+2]=s[i];

        str[i*2+3]='#';

    }

    len2=len1*2+2;

    str[len2]=')';

}

void Manacher(){

    memset(p,0,sizeof(p));

    int id=0,mx=0;

    ll ans=0;

    for(int i=1;i<len2;i++){

        if(mx>i) p[i]=min(mx-i,p[2*id-i]);

        else p[i]=1;

        for(;str[i+p[i]]==str[i-p[i]];p[i]++);

        if(p[i]+i>mx){

            mx=p[i]+i;

            id=i;

        }

        ans+=p[i]/2;

    }

    printf("%lld\n",ans);

}

int main(){

    scanf("%s",s);

    init();

    Manacher();

    return 0;

}

巴特西

【HIHOCODER 1589】回文子串的数量（Manacher）

描述

输入

输出

样例输入

样例输出

题解

最新文章

热门文章