URAL 1960 Palindromes and Super Abilities(回文ツリー)

題意:文字列を与えて、長さは10万を超えないで、各接頭辞の本質の異なっている回文列の個数を聞きます
リンク:http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=45002
解法:この問題は重み付けに関して、manacherではそうはいかないようで、接尾辞配列を使うと、また「同じ文字列が異なる位置に分布しているので統計が悪い」という問題に遭遇します.
code

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
#define input freopen("/Users/peteryuanpan/data.txt","r",stdin)

#define N 100010
#define M 26
char s[N];
int lens;

class Palindromic_Tree{
public:
    int fail[N];
    int next[N][M];
    int num[N];
    int cnt[N];
    int len[N];
    int S[N];
    int last, n, p;
    int new_node(int l){
        for(int i = 0; i < M; i++) next[p][i] = 0;
        num[p] = 0;
        cnt[p] = 0;
        len[p] = l;
        return p++;
    }
    void init(){
        p = 0;
        new_node(0);
        new_node(-1);
        last = n = 0;
        S[n] = -1;
        fail[0] = 1;
        fail[1] = 0;
    }
    int get_fail(int x){
        while(S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }
    void add(int c){
        c -= 'a';//may be changed
        S[++n] = c;
        int cur = get_fail(last);
        if(next[cur][c] == 0){
            int now = new_node(len[cur] + 2);
            fail[now] = next[get_fail(fail[cur])][c];
            next[cur][c] = now;
            num[now] = num[fail[now]] + 1;
        }
        last = next[cur][c];
        cnt[last]++;
    }
    void count(){
        for(int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
}pt;

int main(){
    //input;
    scanf("%s", s);
    lens = (int)strlen(s);
    pt.init();
    for(int i = 0; i < lens; i++){
        pt.add(s[i]);
        printf("%d%c", pt.p - 2, i + 1 == lens ? '
' : ' ');
    }
    return 0;
}