回文树

　　回文树能解决的问题：

　　　　a.求串S不同的回文串的个数。

　　　　b.求串S内每个不同回文串出现的次数。

　　　　c.求串S内回文串的个数。

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

　　回文树一般构建两棵树，一棵表示奇数长度的树为-1，另一棵表示偶数长度的树为“”。

　　其中，回文树的fail指针同AC自动机其实是有相似之处的，fail指针是指向改串的最长回文后缀的。AC自动机的fail指针是使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。但回文树是在线构造的。其他与AC自动机和KMP有很多相似之处。