回文串计数-Manacher
传送门:http://codeforces.com/problemset/problem/159/D
题目大意:给你一个回文串，问你有多少对不相交的回文串对数.
题目思路：
解法一:dp预处理 + 后缀和预处理. )
首先我们利用dp预处理dp[i][j]代表区间[i][j]是不是一个回文串.
然后利用dp值计算每个后缀[x,n]中有多少个回文子串，记作aft[].
然后再枚举前缀以y为结尾的回文串有多少个.
O(n)扫描前后缀分割点,计数相乘即可。
AC代码:http://codeforces.com/contest/159/submission/91638194
解法二:Manacher + 差分前缀和 )
注意到我们可以利用Manacher得到的p数组来表示一系列回文串。
由于回文串的单调性,区间[i , i + p[i] - 1]中每个位置上都能够得到位置i的一个回文贡献。
所以我们很容易利用p数组,配合差分的思想来O(n)的计算以y结尾的回文串的个数。即通过p[i]算贡献即可.
前缀后缀都这么处理一遍即可。
不过注意:我们只关注 字符串数组[i] != '#' 的那些点。因为 "以...结尾的回文串"一定要落在字母上才有意义.
AC代码:http://codeforces.com/contest/159/submission/91640539