【回文樹】HDU - 6599 - I Love Palindrome String

題目連結http://acm.hdu.edu.cn/showproblem.php?pid=6599

題意

給出一個字元串，統計有長度為1~n好串的個數。

好串的定義為：本身是回文串，左半邊也是回文串。

題解

先用回文樹跑一遍，對于每個本質不同的回文串進行判斷，累加答案即可。至于判斷，可以用馬拉車等方法。但觀察一下也可以發現，如果目前串長 t 1 t1 t1，和最長字尾回文串長 t 2 t2 t2滿足關系： ( t 1 / 2 ) % ( t 1 − t 2 ) = = 0 (t1/2)\%(t1-t2)==0 (t1/2)%(t1−t2)==0，該串就是好串。

參考大佬部落格：https://www.cnblogs.com/Chen-Jr/p/11240112.html

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+7;
struct PAM{//回文樹
    int nxt[N][26],fail[N],len[N],cnt[N],str[N];
    int tot,n,lst;
    int newnode(int x){
        for(int i=0;i<26;i++) nxt[tot][i]=0;
        cnt[tot]=0;
        len[tot]=x;
        return tot++;
    }
    void init(){
        tot=lst=n=0;
        newnode(0);
        newnode(-1);
        fail[0]=1;
        str[0]=-1;
    }
    int getfail(int x){
        while(str[n-len[x]-1]!=str[n]) x=fail[x];
        return x;
    }
    void ist(int c){
        str[++n]=c;
        int cur=getfail(lst);
        if(!nxt[cur][c]){
            int now=newnode(len[cur]+2);
            fail[now]=nxt[getfail(fail[cur])][c];
            nxt[cur][c]=now;
        }
        lst=nxt[cur][c];
        cnt[lst]++;
    }
    void getsum(){
        for(int i=tot-1;i>=0;i--){
            cnt[fail[i]]+=cnt[i];
        }
    }
}pam;
char s[N];
int ans[N];
bool ck(int x){
    int t1=pam.len[x];
    int t2=pam.len[pam.fail[x]];
    return ((t1/2)%(t1-t2))==0;
}
int main(){
    while(scanf("%s",s)!=EOF){
        pam.init();
        int sz=strlen(s);
        for(int i=0;i<sz;i++){
            pam.ist(s[i]-'a');
            ans[i+1]=0;
        }
        pam.getsum();
        for(int i=0;i<pam.tot;i++){
            if(ck(i)) ans[pam.len[i]]+=pam.cnt[i];
        }
        for(int i=1;i<=sz;i++){
            printf("%d%c",ans[i],i==sz?'\n':' ');
        }
    }
}