Harry and magic string

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 576 Accepted Submission(s): 287

Problem Description

Harry got a string T, he wanted to know the number of T’s disjoint palindrome substring pairs. A string is considered to be palindrome if and only if it reads the same backward or forward. For two substrings of T:x=T[a1…b1],y=T[a2…b2](where a1 is the beginning index of x,b1 is the ending index of x. a2,b2 as the same of y), if both x and y are palindromes and b1<a2 or b2<a1 then we consider (x, y) to be a disjoint palindrome substring pair of T.

Input

There are several cases.
For each test case, there is a string T in the first line, which is composed by lowercase characters. The length of T is in the range of [1,100000].

Output

For each test case, output one number in a line, indecates the answer.

Sample Input

aca aaaa

Sample Output

3 15

Hint

For the first test case there are 4 palindrome substrings of T. They are: S1=T[0,0] S2=T[0,2] S3=T[1,1] S4=T[2,2] And there are 3 disjoint palindrome substring pairs. They are: (S1,S3) (S1,S4) (S3,S4). So the answer is 3.

Source

BestCoder Round #25

Recommend

heyang | We have carefully selected several similar problems for you: 6447 6446 6445 6444 6443

题意：

在一个S串中找两个回文串，两个回文串没有重叠的部分。问有多少个这样的回文串对。

思路：

用manacher我们可以求出以$i$为中心的回文串的个数。

$pre[i]$表示以$i$为开头的回文串的个数，$suf[i]$表示以$i$为结尾的回文串的个数。

那么我们要求的答案其实就是$\sum_{i = 1}^{len} pre[i] * (\sum_{j=1}^{i-1} suf[j])$

所以我们再用一个数组$sum$来存$suf$数组的前缀和。

那么$pre$和$suf$怎么求呢？

我们manacher处理出的$p[i] /2$表示的是以$i$为中心的回文的个数。

那么对于$i$之前的半径内的字符，他们的$pre$可以$+1$。同样他之后的半径内的字符，$suf$可以$-1$

暴力统计肯定是不行的，我们可以使用差分的思想。

对于$[i,j]$区间内的每一个数都更新$k$的话，我们可以用一个数组$add[i] += k$,add[j+1] -=k$

然后从前往后求前缀和得到的就是对区间的全部更新了。求$suf$和$pre$也是同样的道理。

$pre$是后面影响前面的所以从后往前求“#”向前靠，$suf$从前往后求“#”向后靠。

 #include<iostream>

 //#include<bits/stdc++.h>

 #include<cstdio>

 #include<cmath>

 //#include<cstdlib>

 #include<cstring>

 #include<algorithm>

 //#include<queue>

 #include<vector>

 //#include<set>

 //#include<climits>

 //#include<map>

 using namespace std;

 typedef long long LL;

 #define N 100010

 #define pi 3.1415926535

 #define inf 0x3f3f3f3f

 const int maxn = 1e5 + ;

 char s[maxn], ss[maxn * ];

 LL pre[maxn * ], suf[maxn * ], sum[maxn * ];

 int lens, p[maxn * ];

 int init()

 {

     ss[] = '$';

     ss[] = '#';

     int lenss = ;

     for(int i = ; i < lens; i++){

         ss[lenss++] = s[i];

         ss[lenss++] = '#';

     }

     ss[lenss] = '\0';

     return lenss;

 }

 void manacher()

 {

     int lenss = init();

     int id, mx = ;

     for(int i = ; i < lenss; i++){

         if(i < mx){

             p[i] = min(p[ * id - i], mx - i);

         }

         else{

             p[i] = ;

         }

         while(ss[i - p[i]] == ss[i + p[i]])p[i]++;

         if(mx < i + p[i]){

             id = i;

             mx = i + p[i];

         }

     }

 }

 int main()

 {

     while(scanf("%s", s) != EOF){

         lens = strlen(s);

         /*for(int i = 0; i < lens * 2 + 3; i++){

             p[i] = 0;

         }*/

         for(int i = ; i < lens + ; i++){

             suf[i] = pre[i] = sum[i] = ;

         }

         manacher();

         for(int i = ; i <= lens * ; i++){

             int x = (i + ) / ;//向上取整

             suf[x]++, suf[x + (p[i] / )]--;

         }

         for(int i = lens * ; i >= ; i--){

             int x = i / ;

             pre[x]++, pre[x - (p[i] / )]--;

         }

         for(int i = lens; i >= ; i--){

             pre[i] += pre[i + ];

         }

         for(int i = ; i <= lens; i++){

             suf[i] += suf[i - ];

             sum[i] += sum[i - ] + suf[i];

         }

         LL ans = ;

         for(int i = ; i <= lens; i++){

             ans += (LL)pre[i] * sum[i - ];

         }

         printf("%I64d\n", ans);

     }

     return ;

 }

巴特西

hdu5157 Harry and magic string【manacher】

Harry and magic string

最新文章

热门文章