思路

回文自动机

回文自动机的fail[i]就是编号为i的这个字符串的最长的回文后缀的编号，然后len[i]表示编号为i的回文串的长度，cnt[i]表示编号为i的回文串的出现次数

然后trans边就是同时在两边加上一个字符，fail边就是跳fail

然后初始有一个0节点，len为0，fail[0]=1，s[0]=-1，表示长度为2的回文串（s[i-1]和s[i]），另一个1节点，len=-1，表示长度为1的回文串（s[i]自身）

然后跳fail就是比较s[i-len[p]-1]==s[i]，满足证明找到了，否则继续往上跳

然后子节点的fail就是它父亲的fail的对应转移边（类似AC自动机

然后就没有了

代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN = 300010;int len[MAXN],cnt[MAXN],fail[MAXN],trans[MAXN][26],s[MAXN],Nodecnt,last,n;char S[MAXN];long long ans=0;int New_state(int _len){    len[Nodecnt]=_len;    return Nodecnt++;}int get_fail(int p,int n){    while(s[n-len[p]-1]!=s[n])        p=fail[p];    return p;}void add_len(int n){    int cur=get_fail(last,n);    if(!trans[cur][s[n]]){        int t=New_state(len[cur]+2);        fail[t]=trans[get_fail(fail[cur],n)][s[n]];        trans[cur][s[n]]=t;    }    cnt[trans[cur][s[n]]]++;    last=trans[cur][s[n]];}int main(){    s[0]=-1;    New_state(0);    fail[0]=1;    New_state(-1);    last=0;    scanf("%s",S+1);    n=strlen(S+1);    for(int i=1;i<=n;i++){        s[i]=S[i]-'a';        add_len(i);    }    for(int i=Nodecnt-1;i>=0;i--)        cnt[fail[i]]+=cnt[i];    for(int i=0;i