（最好事先學(xué)習(xí)過kmp，Trie，AC自動(dòng)機(jī)）
回文樹，有效解決各類回文問題的超級(jí)666的樹形結(jié)構(gòu)

集AC自動(dòng)機(jī)的fail，類字典樹的next數(shù)組和結(jié)構(gòu)為一體
假設(shè)存在字符串S: abbaabaabba， 下標(biāo)從0開始，長度l
可以求解：
1、S中本質(zhì)不同的回文串（何為本質(zhì)不同？長度相同回文不同， 長度不同回文有出現(xiàn)重疊或包含）
2、S中本質(zhì)不同的回文串出現(xiàn)的次數(shù)，及其長度
3、S中以i結(jié)尾的回文數(shù)；

(S中本質(zhì)不同的回文串有 aa, bb, aba, abba, aabaa, baabaab, bbaabaabb, abbaabaabba)

回文樹結(jié)構(gòu)
1、初始時(shí)有兩個(gè)節(jié)點(diǎn)0（回文長度為偶數(shù)）， 1（回文長度為奇數(shù)）
2、有匹配失敗進(jìn)行跳轉(zhuǎn)的fail[]指針（可類AC自動(dòng)機(jī)）
3、有計(jì)算公共前后綴的next[][]（也可用鄰接表）（類字典樹）

//鄰接矩陣Time：249ms,  Memory: 12704kB
#include <cstdio>
#include <cstring>
const int M = 100005;

struct PAT
{
    int next[maxn][N];//next指針,和字典樹類似，指向的串為當(dāng)前串兩端加上同一個(gè)字符構(gòu)成。
    int fail[maxn];//失配后跳轉(zhuǎn)到fail指針指向的節(jié)點(diǎn)
    int cnt[maxn];//節(jié)點(diǎn)i處本質(zhì)不同的回文串個(gè)數(shù)
    int num[maxn];
    int len[maxn];  
    int last, n, p;

    int Create(int rt)
    {
        for (int i = 0; i < 26; i++) next[p][rt] = 0;
        cnt[p] = 0;
        num[p] = 0;
        len[p] = rt;
        return p++;
    }

    void Init()
    {
        p = last = n = 0;
        Create(0);
        Create(-1);
        S[n] = -1;
        fail[0] = 1;
    }

    int getFail(int x) //fail指針的構(gòu)建
    {
        while (S[n-len[x]-1] != S[n]) x = fail[x];
        return x;
    }

    void Insert(int c) //插入字符
    {
        c -='a';
        S[++n] = c;
        int cur = getFail(last);
        if (!next[cur][c])//如果不存此字符節(jié)點(diǎn)
        {
            int now = Create(len[cur]+2); //+2：回文所以兩段同時(shí)加1
            fail[now] = next[ getFail(fail[cur]) ][c];//構(gòu)建此處的fail
            next[cur][c] = now;//構(gòu)建此處的next
            num[now] = num[ fail[now] ] + 1;
        }
        last = next[cur][c]; //last指針
        cnt[last]++;
    }

    void Count()
    {
        for (int i = p-1; i >= 0; i--)
            cnt[ fail[i] ] += cnt[i]; //父節(jié)點(diǎn)累加子節(jié)點(diǎn)的cnt（若fail[v]=u,則u一定是v的子回文串）
    }

} PaTree;


int main()
{
    char str[M];
    scanf("%s", str);
    PaTree.Init();
    int len = strlen(str);
    for (int i = 0; i < len; i++)
        PaTree.Insert(str[i]);
        printf("%d", PaTree.p-2);

    return 0;
}

//鄰接表Time：234ms；Memory：5284kB
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define CLR(x) memset(x,0,sizeof(x))
#define mod 9973
#define man 262144
const int maxn = 100005;

struct PAM
{
    vector<pair<int,int> > next[maxn];
    int fail[maxn], num[maxn],len[maxn], cnt[maxn];
    int s[maxn], n, p, last;

    int newnode(int w)
    {
        next[p].clear();
        cnt[p]=num[p]=0;
        len[p]=w;
        return p++;
    }
    void init()
    {
        p = 0;
        newnode(0);
        newnode(-1);
        last = 0;
        n = 0;
        s[n] = -1;
        fail[0] = 1;
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1] != s[n]) x = fail[x];
        return x;
    }
    void add(int c)
    {
        c -= 'a';
        s[++n] = c;
        int cur = get_fail(last);
        int flag = 0;
        for(int i=0; i<next[cur].size(); i++)
            if(next[cur][i].first==c)
            {
                last = next[cur][i].second;
                cnt[last]++;
                return ;
            }
        int now = newnode(len[cur]+2);
        int fi = get_fail(fail[cur]);
        flag = 0;
        for(int i=0; i<next[fi].size(); i++)
            if(next[fi][i].first==c)
            {
                flag = next[fi][i].second;
                break;
            }
        fail[now] = flag;
        next[cur].push_back(make_pair(c,now));
        num[now] = num[flag] + 1;
        last = now;
        cnt[now]++;
    }
    void count()
    {
        for(int i=p-1; i>1; i--)
        {
            cnt[fail[i]] += cnt[i];
        }
    }
} PaTree;

int main()
{
    char str[maxn];
    scanf("%s", str);
    PaTree.init();
    int len = strlen(str);
    for (int i = 0; i < len; i++)
    {
        PaTree.add(str[i]);
        printf("%d", PaTree.p-2);
        if (i != len-1) printf(" ");
    }
    return 0;
}