回文树（附模板题URAL-1960）

（最好事先学习过kmp，Trie，AC自动机）
回文树，有效解决各类回文问题的超级666的树形结构

集AC自动机的fail，类字典树的next数组和结构为一体
假设存在字符串S: abbaabaabba， 下标从0开始，长度l
可以求解：
1、S中本质不同的回文串（何为本质不同？长度相同回文不同， 长度不同回文有出现重叠或包含）
2、S中本质不同的回文串出现的次数，及其长度
3、S中以i结尾的回文数；

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

回文树结构
1、初始时有两个节点0（回文长度为偶数）， 1（回文长度为奇数）
2、有匹配失败进行跳转的fail[]指针（可类AC自动机）
3、有计算公共前后缀的next[][]（也可用邻接表）（类字典树）

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

struct PAT
{
    int next[maxn][N];//next指针,和字典树类似，指向的串为当前串两端加上同一个字符构成。
    int fail[maxn];//失配后跳转到fail指针指向的节点
    int cnt[maxn];//节点i处本质不同的回文串个数
    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指针的构建
    {
        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])//如果不存此字符节点
        {
            int now = Create(len[cur]+2); //+2：回文所以两段同时加1
            fail[now] = next[ getFail(fail[cur]) ][c];//构建此处的fail
            next[cur][c] = now;//构建此处的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]; //父节点累加子节点的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;
}