杭電多校第二場 I Love Palindrome String （Pam+Hash）

給你一個字元串，問長度為0~|s| 滿足l~r為回文串 并且l~(l+r)/2 也為回文串的數量

由題意可知如果長度為偶數則 需要滿足l~(l+r)/2 == (l+r)/2+1~r

如果長度為奇數則需要滿足l~(l+r)/2==(l+r)/2~r 

對于回文樹上的每個節點，我們預處理每個節點的回文串的末尾字元所在的下标 然後hash特判回文串是否滿足

然後根據長度累計答案

#include<bits/stdc++.h>//空間O(N*字元集大小) 時間O(N*log(字元集大小))
#define ll long long
#define ull unsigned long long
#define maxn 300010   //節點個數
using namespace std;
const ull base=201326611;
char a[maxn];
ll ans[maxn];
ull Hash[maxn];
ull p[maxn];
ull get_hash(int l, int r)
{
    if(l==0)return Hash[r];
    return Hash[r]-Hash[l-1]*p[r-l+1];
}
bool check(int l, int r)
{
    int le=r-l+1;
    int mid=(r+l)>>1;
    if(le&1)
    {
        return get_hash(l,mid)==get_hash(mid,r);
    }
    else return get_hash(l,mid)==get_hash(mid+1,r);
}
struct pam
{
    int len[maxn];  //len[i] 節點i的回文串長度
    int nxt[maxn][26]; //nxt[i]['c'] 節點i的回文串在兩邊添加字元c後變成的回文串編号
    int fail[maxn]; //fail[i] 指向i的最長回文字尾所在的節點 且不為i
    int cnt[maxn]; //cnt[i] 節點i表示的回文串在S中出現的次數
    int s[maxn]; //s[i] 第i次添加的字元
    int num[maxn];
    int id[maxn];
    int last; //指向以字元串中上一個位置結尾的回文串的節點
    int cur; //指向由next構成的樹中目前回文串的父親節點（即目前回文串是cur左右兩邊各拓展一個字元得來）
    int p; // 添加的節點個數
    int n; // 添加的字元串個數
    int newnode(int l)  //建立節點
    {
        for(int i=0;i<=25;i++)nxt[p][i]=0; // 消除子節點
        cnt[p]=num[p]=0;  //節點p為新回文串是以出現次數為0
        len[p]=l;
        return p++;
    }
    inline void init()
    {
        p=n=last=0;
        newnode(0);  //偶節點
        newnode(-1); //奇節點
        s[0]=-1;
        fail[0]=1;
    }
    int get_fail(int x) //找到可以插入的節點
    {
        while(s[n-1-len[x]]!=s[n])x=fail[x];
        return x;
    }
    inline void add(int c)
    {
        c-='a';
        s[++n]=c;
        int cur=get_fail(last); // 找到可以插入的節點并當做父節點
        if(!nxt[cur][c])
        {
            int now=newnode(len[cur]+2);
            fail[now]=nxt[get_fail(fail[cur])][c]; //從父節點的回文字尾開始找,找到一個s[l-1]=s[n]的點則出邊的點為最長回文字尾
            nxt[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=nxt[cur][c];  //成為新的上一個位置
        id[last]=n;
        cnt[last]++;
    }
    void Count() //統計本質相同的回文串的出現次數。與位置無關
    {
        for(int i=p-1;i>=0;i--)
        {
            cnt[fail[i]]+=cnt[i]; //每個節點會比父節點先算完，于是父節點能加到所有的子節點
        }
        for(int i=2;i<p;i++)
        {
            if(check(id[i]-len[i],id[i]-1))
            {
                ans[len[i]]+=cnt[i];
            }
        }
    }
}pam;
int main()
{
    p[0]=1;
    for(int i=1;i<maxn;i++)p[i]=p[i-1]*base;
    while(scanf("%s",a)!=EOF)
    {
        memset(ans,0,sizeof(ans));
    int len=strlen(a);
    Hash[0]=a[0];
    for(int i=1;i<len;i++)
    {
        Hash[i]=Hash[i-1]*base+a[i];
    }
    pam.init();
    for(int i=0;i<len;i++)
    {
        pam.add(a[i]);
    }
    pam.Count();
    for(int i=1;i<=len;i++)
    {
        printf("%lld",ans[i]);
        if(i!=len)printf(" ");
        else printf("\n");
    }
    }
    return 0;
}