回文树小结

回文树是一个用来解决回文串相关问题的数据结构。回文树由若干个节点组成，每个节点代表一个回文串。

相比于manacher，回文树要显得强大的多，同样是接近o(n)的复杂度，回文树只需要多一点的空间，就可以实现许多用manacher实现起来非常复杂的功能，并且能解决很多关于回文串的问题。

节点之间通过有向边连接起来，回文树中有两种类型的边：

第一种类型的边上同时有字符做标记，比如：u和v通过带字符x通过带字符u所表示的回文串两边添加x字符可以得到v节点所表示的回文串。

另一种类型的边是后缀链接边，从u到v存在一条后缀链接边，当且仅当v节点所代表的回文串是的后缀中最长的回文串，但u和v不能相同（这条边其实类似于ac自动机的fail指针）

回文树这个数据结构并不是一棵普通的树，它有两个根，分别存储偶数回文串树和存储奇数回文串树组成，一个根表示长度为-1的回文串，是我们为了方便操作加进去的，长度为1的回文串可以通过它左右两侧各添加一个字符得到。另一个根表示长度为0的回文串，即空串。

我们并不在每个节点中实际存储它所表示的回文串，否则很容易爆内存，节点中仅仅包含如下信息：1.回文串长度2.通过所有字符连接的边（即第一种类型的边）3.后缀链接边（即第二种类型的边）。还有其它根据实际问题需要添加的边。

回文树能做到如下几点：

1.求串S前缀0~i内本质不同回文串的个数
2.求串S内每一个本质不同回文串出现的次数
3.求串S内回文串的个数

4.求以下标i结尾的回文串的个数

总结一下回文树的妙用以及稍稍的优化策略大概有以下几点：
1.节点数减2是本质不同的回文子串数量。
2.统计全部回文子串可以考虑先记录每个点的cnt, 到最后向拓扑排序一样往fail(后缀匹配失败指针)对应的节点累加。
3.如果在线统计的话，每个点的cnt可以代表该回文串对应的后缀回文子串的数量，然后动态加动态统计。
4.如果动态在字符串末尾加入字母和删除的操作，因为回文树每次加入, 改变的是last指针的位置，以及是否新加入一个节点,可以开一个last数组来保存之前的位置，退回的时候还原last即可，这样就不需要删除操作。

5.如果前后都可以加字母的操作，这种的话就是为前后开两个last来记录位置，因为是回文串，所以左右是相同的，fail指针是通用的，需要注意的地方是当整个串是回文的时候要把前后两个last合并在一起（具体可以看http://blog.csdn.net/a664607530/article/details/78197193）。

struct PalindromicTree  
{  
    const static int maxn = 1e6 + 10;  
    int next[maxn][26], last, sz, tot;  
    int fail[maxn], len[maxn];  
    LL cnt[maxn];  
    char s[maxn];  
    void Clear()  
    {  
        len[1] = -1; len[2] = 0;  
        fail[2] = fail[1] = 1;  
        last = (sz = 3) - 1;  
        cnt[1] = cnt[2] = tot = 0;  
        memset(next[1], 0, sizeof(next[1]));  
        memset(next[2], 0, sizeof(next[2]));  
    }  
    int Node(int length)  
    {  
        memset(next[sz], 0, sizeof(next[sz]));  
        len[sz] = length, cnt[sz] = 0;  
        return sz++;  
    }  
    int getfail(int x)  
    {  
        while (s[tot] != s[tot - len[x] - 1]) x = fail[x];  
        return x;  
    }  
    int add(char pos)  
    {  
        int x = (s[++tot] = pos) - 'a', y = getfail(last);  
        if (next[y][x]) return cnt[last = next[y][x]];  
        last = next[y][x] = Node(len[y] + 2);  
        fail[last] = len[last] == 1 ? 2 : next[getfail(fail[y])][x];  
        cnt[last] += 1 + cnt[fail[last]];  
        return cnt[last];  
    }  
}solve;