HDU 5785 Interesting （manacher+区间处理）

HDU 5785 Interesting （manacher+区间处理）

Interesting

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 595    Accepted Submission(s): 227

Problem Description

Alice get a string S. She thinks palindrome string is interesting. Now she wanna know how many three tuple (i,j,k) satisfy1≤i≤j

Input

The input contains multiple test cases. Each test case contains one string. The length of string is between 1 and 1000000. String only contains lowercase letter.

Output

For each test case output the answer mod 1000000007.

Sample Input

aaa abc

Sample Output

14 8

Author

ZSTU

Source

​​2016 Multi-University Training Contest 5​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5803​​​ ​​5802​​​ ​​5801​​​ ​​5800​​​ ​​5799​​

题意：有一个长度为n的串（n<=10^6），对 1 <= i <= j < k <= length(s) .  如果【i，j】和【j+1,k】都是回文串。则对答案的贡献为 i*k ,求贡献和。

题解：

在O（n）时间内算出左右的回文个数。

用Manacher处理出每个字符的回文半径。如果用 L[i] 表示以i结尾的回文串的左端点坐标值之和，R[i]表示以i开头的右端点的坐标值之和。那么显然答案就是

。接下来要求的就是L【i】和R【i】。以L[i]为例，一个中心为i半径为l的回文串对属于【i−l+1,i】的

L [ i ] 值都是有贡献的，且对于

的贡献为  i +（i - j）, 那么，

。

其中j是包含i的回文串的对称轴坐标，k是i被包含在回文串左半边的次数。

因为没有动态的修改，所以只要 O(n)处理即可。R[i]同理。

这题可以直接在Manacher处理的回文半径上直接计算，对于

，对 L[i]  的贡献为

对于对称轴为#的情况同样适用。

因此，

。

在计算最后的答案时只要每次+=2就可以了。

注意：在manacher中串长是原串的2倍。

如果有一个长串是回文串，那它的某一中心串也是回文串。

AC代码：

#includeusing namespace std;const int mod=1e9+7;const int maxn=1e7;char str[maxn];int n,L;int p[maxn];char s[maxn];/*data[1]表示以当前点为右边界的所有回文串的中心的和的两倍。data[2]表示以当前点为右边界的所有回文串的个数。data[3]表示以当前点为左边界的所有回文串的中心的和的两倍。data[4]表示以当前点为左边界的所有回文串的个数。*/int data[5][2000100];//manacher预处理 void init(){ memset(data,0,sizeof(data)); n=strlen(s); str[0]='@'; str[1]='#'; for(int i=0;ii) { p[i]=min(p[2*id-i],mx-i); //mx-i写成p[id]+id-i也行 } else p[i]=1; while(str[i+p[i]]==str[i-p[i]]) p[i]++; if(p[i]+i>mx) { mx=p[i]+i; id=i; } }}// void add(int op,int l,int r,int num){ if (l>r) return ; data[op][l] += num; data[op][l] %= mod; data[op][r+1] -= num; data[op][r+1] %= mod;}int main(){ while(~scanf("%s",s)) { init(); manacher(); for(int i=L-1;i>=1;--i) //右边 { add(1,i-p[i]+1,i,i); //data[1] add(2,i-p[i]+1,i,1); //data[2] } for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。