题解

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tot;
ll ans,p1[20001],p2[20001];
struct node{
    int fail,ch[26],len,cnt,dep;
}t[200001];
char s[200001];
 
int read()
{
    int x=0,w=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
 
void solve1()
{
    int len=strlen(s+1),k=0;s[0]='#';
    t[0].fail=t[1].fail=1;t[1].len=-1;tot=1;
    for(int i=1;i<=len;i++)
    {
        while(s[i-t[k].len-1]!=s[i])k=t[k].fail;
        if(!t[k].ch[s[i]-'a']){
            t[++tot].len=t[k].len+2;
            int j=t[k].fail;
            while(s[i-t[j].len-1]!=s[i])j=t[j].fail;
            t[tot].fail=t[j].ch[s[i]-'a'];
            t[k].ch[s[i]-'a']=tot;
            t[tot].dep=t[t[tot].fail].dep+1;
        }
        k=t[k].ch[s[i]-'a'];
        p1[i]=t[k].dep;
        t[k].cnt++;
    }
}
 
 
void solve2()
{
    int len=strlen(s+1),k=0;s[0]='#';
    t[0].fail=t[1].fail=1;t[1].len=-1;tot=1;
    for(int i=1;i<=len;i++)
    {
        while(s[i-t[k].len-1]!=s[i])k=t[k].fail;
        if(!t[k].ch[s[i]-'a']){
            t[++tot].len=t[k].len+2;
            int j=t[k].fail;
            while(s[i-t[j].len-1]!=s[i])j=t[j].fail;
            t[tot].fail=t[j].ch[s[i]-'a'];
            t[k].ch[s[i]-'a']=tot;
            t[tot].dep=t[t[tot].fail].dep+1;
        }
        k=t[k].ch[s[i]-'a'];
        t[k].cnt++;
        p2[len-i+1]=t[k].dep;
    }
}
 
 
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    solve1();
    reverse(s****+len+1);
    memset(t,0,sizeof(t));
    solve2();
    for(int i=1;i<=len;i++)p1[i]+=p1[i-1];
    for(int i=1;i<=len;i++)ans+=p1[i]*p2[i+1];
    printf("%lld",ans);
    return 0;
}

可以给个关注吗，我会持续发题解的