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

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

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
点赞 评论 收藏
分享
ZywOo_求职版:谁问你了....
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务