SPOJ NUMOFPAL 回文樹

題目連結：點我點我:-)

題目描述：

給一個字元串，求其本質不同的回文子串數目（字元串長度<=1000）

思路：

這是一個非常好的講解

建立回文樹，每次在最後停留的節點上計數器加一，

最後從父親累加兒子的cnt，因為如果pre[v]=u，則u一定是v的子回文串

代碼：

//miaomiao 2017.3.25
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define N (1000+5)

char s[N];
int ans;

struct Palin_Tree{
    int ch[N][], pre[N], len[N], cnt[N], Tot, last;

    void init(){
        Tot = ; last = ;
        len[] = -; pre[] = ;
    }

    int getfail(int id, int nl){
        while(s[id-len[nl]-] != s[id]) nl = pre[nl];
        return nl;
    }

    void Add(int id, char c){
        c -= 'a';

        int nl = getfail(id, last);
        if(!ch[nl][c]){
            int p = ch[nl][c] = ++Tot;
            len[p] = len[nl]+;
            pre[p] = ch[getfail(id, pre[nl])][c];
            if(pre[p] == p) pre[p] = ;
        }

        last = ch[nl][c]; ++cnt[last];
    }

    void Count(){
        Forr(i, Tot, ) cnt[pre[i]] += cnt[i];
        For(i, , Tot) ans += cnt[i];
        printf("%d\n", ans);
    }
}PT;

int main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif

    PT.init();
    scanf("%s", s+); s[] = ;

    For(i, , strlen(s+)) PT.Add(i, s[i]);
    PT.Count();

    return ;
}