题目：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=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
struct data{
ll sum;
int n,tot,fail[maxn],l[maxn],nxt[maxn][],s[maxn],last,cnt[maxn];
int newnode(int len){
clr(nxt[tot],);
l[tot]=len; cnt[tot]=;
return tot++;
}
void init(){
tot=; sum=; clr(fail,);
newnode(); newnode(-);
fail[]=;
last=;
s[]=-;
n=;
}
int getfail(int v){
while (s[n-l[v]-]!=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]+);
fail[now]=nxt[getfail(fail[cur])][c];
nxt[cur][c]=now;
cnt[now]=cnt[fail[now]]+;
} last=nxt[cur][c];
return cnt[last];
}
}T;
int main(){
// freopen("in.txt","r",stdin);
while (~scanf("%s",ch)){
clr(a,); ans=;
int len=strlen(ch);
T.init();
down(i,len-,){
a[i]=a[i+]+T.add(ch[i]-'a');
}
// down(i,len-1,0) printf("%lld ",a[i]);
T.init();
rep(i,,len-) {
ans+=a[i+]*T.add(ch[i]-'a');
}
printf("%lld\n",ans);
}
return ;
}