hdu 5157(树状数组+Manacher)

Harry and magic string

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

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

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

题意:找到一个串中不相交的回文串的数量.

题解:官方题解:

先求出p[i],表示以i为回文中心的回文半径，manacher，sa，hash都可以。然后我们考虑以i为回文中心的时候，可以贡献出多少答案。我们先考虑长度为p[i]的那个回文子串，它能贡献的答案，就是末尾在i-p[i]之前的回文子串数，那么长度为p[i-1]的，也是同样的道理。所以我们需要求一个f[x]，表示末尾不超过x的回文子串总共有多少个，把f[i-p[i]]到f[i-1]累加起来即为以i为中心的回文子串能贡献的答案。那我们先统计，以x为结尾的回文子串有多少个，设为g[x]。来看以j为中心的回文子串，它的回文半径是p[j]，那么从j到j+p[j]-1的这一段，都会被贡献一个回文子串，也就是这一段的g[]会被贡献1，这里的处理方法很多，不细说。然后求一次前缀和，即可得到f[x]。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 100005;
char s[2*N],t[2*N];
char str[2*N];
int p[2*N];
int c[2*N];
LL l[2*N];
void manacher(int n)
{
    int id =0,maxr=0;
    p[0]=1;
    for(int i=1; i<2*n+1; i++)
    {
        if(p[id]+id>i)
            p[i]=min(p[2*id-i],p[id]+id-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])
            ++p[i];
        if(id+p[id]<i+p[i]) id=i;
        if(maxr<p[i])
            maxr=p[i];
    }
}
int lowbit(int x)
{
    return x&-x;
}
void update(int idx,int v)
{
    for(int i=idx; i<=2*N; i+=lowbit(i))
    {
        c[i]+=v;
    }
}
int getsum(int idx)
{
    int sum = 0;
    for(int i=idx; i>0; i-=lowbit(i))
    {
        sum+=c[i];
    }
    return sum;
}
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int n=strlen(str);
        s[0]='#';
        for(int i=1; i<=n; i++)
        {
            s[2*i]='#';
            s[2*i-1]=str[i-1];
        }
        manacher(2*n);
        memset(c,0,sizeof(c));
        for(int i=1; i<=2*n; i++)
        {
            int ori;
            if(i%2==0) ori = i/2+1;
            else ori = (i+1)/2;
            int ori1 = (i+p[i]-1)/2+1;
            if(ori1<=ori) continue;
            update(ori,1);
            update(ori1,-1);
        }
        memset(l,0,sizeof(l));
        for(int i=1; i<=n; i++)
        {
            l[i] = l[i-1]+getsum(i);
        }
        reverse(s,s+2*n+1);
        manacher(2*n);
        memset(c,0,sizeof(c));
        for(int i=1; i<=2*n; i++)
        {
            int ori;
            if(i%2==0) ori = i/2+1;
            else ori = (i+1)/2;
            int ori1 = (i+p[i]-1)/2+1;
            if(ori1<=ori) continue;
            update(ori,1);
            update(ori1,-1);
        }
        LL ans = 0;
        for(int i=1; i<=n; i++)
        {
            ans += getsum(i)*l[n-i];
        }
        printf("%lld
",ans);
    }
    return 0;
}