这题建立一棵回文树，然后用dfs搜索答案，但是有一点需要注意，就是打vis的标记时，如果标记为1，那么在好几个节点都对同一个字符i打过标记，此时的搜索从字符i点回溯，回到它的父亲节点，搜索其它的字符，回溯的时候把vis[i]标记成0了，之前的vis[i]标记全被清空了，如果该父亲的其它字符节点下，有字符i的孩子，则此时统计就会出错。所以打vis标记的时候让vis++，而不是标记为0。
#include <iostream> #include <stdio.h> using namespace std; const int MAXN=3e5+10; const int N=26; char str[MAXN]; struct PAM { int len[MAXN]; int num[MAXN]; int s[MAXN]; int fail[MAXN]; int next[MAXN][N]; int cnt[MAXN]; int last,p,n; int newNode(int l) { for (int i=0;i<N;i++) next[p][i]=0; cnt[p]=0; num[p]=0; len[p]=l; return p++; } void init() { n=0; p=0; last=0; newNode(0); newNode(-1); fail[0]=1; s[0]=-1; } int getFail(int x) { while (s[n-len[x]-1]!=s[n]) x=fail[x]; return x; } void add(int c) { c-='a'; s[++n]=c; int cur=getFail(last); if (!next[cur][c]) { int now=newNode(len[cur]+2); fail[now]=next[getFail(fail[cur])][c]; next[cur][c]=now; num[now]=num[fail[now]]+1; } last=next[cur][c]; cnt[last]++; } void count() { for (int i=p-1;i>=0;i--) { cnt[fail[i]]+=cnt[i]; } } }pt; int vis[N]; long long ans=0; void dfs(int x,int cnt) { ans+=cnt*pt.cnt[x]; for (int i=0;i<N;i++) { if (pt.next[x][i]) { if (!vis[i]) { vis[i]++; dfs(pt.next[x][i],cnt+1); vis[i]--; } else { dfs(pt.next[x][i],cnt); } } } } int main() { pt.init(); scanf("%s",str); for (int i=0;str[i];i++) { pt.add(str[i]); } pt.count(); // printf("%d\n",pt.cnt[0]); dfs(0,0); dfs(1,0); printf("%lld\n",ans); return 0; }