回文串计数-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

反过来:CodeForces17E- Palisection

题目大意:让你求相交的回文串对数。

题目思路:考虑用总的减去不相交的即可。