HDU-5157Harry and magic string

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5157

先从后往前插点，在构造回文树时，让cnt[i]+=cnt[fail[i]],然后维护一个后缀和a。

再从前往后插点，每个点对答案的贡献为cnt[i]*a[i+1]

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define ll long long
#define maxn 200500
using namespace std;
ll a[maxn],ans;
char ch[maxn];
int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct data{
    ll sum;
    int n,tot,fail[maxn],l[maxn],nxt[maxn][30],s[maxn],last,cnt[maxn];
    int newnode(int len){
        clr(nxt[tot],0);
        l[tot]=len; cnt[tot]=0;
        return tot++;
    }
    void init(){
        tot=0; sum=0; clr(fail,0);
        newnode(0); newnode(-1);
        fail[0]=1;
        last=1;
        s[0]=-1;
        n=0;
    }
    int getfail(int v){
        while (s[n-l[v]-1]!=s[n]) v=fail[v];
        return v;
    }
    int add(int c){
        s[++n]=c;
        int cur=getfail(last);
        if (!nxt[cur][c]){
            int now=newnode(l[cur]+2);
            fail[now]=nxt[getfail(fail[cur])][c];
            nxt[cur][c]=now;
            cnt[now]=cnt[fail[now]]+1;
        } last=nxt[cur][c];
        return cnt[last];
    }
}T;
int main(){
 //   freopen("in.txt","r",stdin);
    while (~scanf("%s",ch)){
        clr(a,0); ans=0;
        int len=strlen(ch);
        T.init();
        down(i,len-1,0){
            a[i]=a[i+1]+T.add(ch[i]-'a');
        }
    //    down(i,len-1,0) printf("%lld ",a[i]);
        T.init();
        rep(i,0,len-1) {
            ans+=a[i+1]*T.add(ch[i]-'a');
        }
        printf("%lld
",ans);
    }
    return 0;
}