【回文树初级】

 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 300010
#define LL long long
using namespace std;

char s[N];
int p,n,now,cur,fail[N],cnt[N],len[N],tot,last,ch[N][26];
int nn=0; 
LL ans;

int newnode(int x,int pos)
{
    len[tot]=x;
    if (x>=1)
    {
    	nn++;
    	kp[nn].aa=pos-x+1;
    	kp[nn].bb=pos-1+1;
    }
    return tot++;
}


int get_fail(int x,int n)
{
    while(s[n-len[x]-1]!=s[n]) x=fail[x];
    return x;
}

int main()
{
    scanf("%d %d\n",&n,&p);
    scanf("%s",s+1);
    s[0]=-1;fail[0]=1;last=0;
    newnode(0,0);newnode(-1,0);
    for(n=1;s[n];++n)
    {
        s[n]-='a';
        cur=get_fail(last,n);\\找到最长的 当前串的回文后缀
        if (!ch[cur][s[n]])  \\若新回文串不存在 就新增
        {
            now=newnode(len[cur]+2,n);  \\新建节点
            fail[now]=ch[get_fail(fail[cur],n)][s[n]]; 
                          \\找用更小的尽量长的拥有s[n]的自己
            ch[cur][s[n]]=now;
        }
        last=ch[cur][s[n]];
    }
    tot--;
    printf("%d\n",tot-1);
    return 0;
}