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 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

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

题解:官方题解:

先求出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 = ;

char s[*N],t[*N];

char str[*N];

int p[*N];

int c[*N];

LL l[*N];

void manacher(int n)

{

    int id =,maxr=;

    p[]=;

    for(int i=; i<*n+; i++)

    {

        if(p[id]+id>i)

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

        else p[i]=;

        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<=*N; i+=lowbit(i))

    {

        c[i]+=v;

    }

}

int getsum(int idx)

{

    int sum = ;

    for(int i=idx; i>; i-=lowbit(i))

    {

        sum+=c[i];

    }

    return sum;

}

int main()

{

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

    {

        int n=strlen(str);

        s[]='#';

        for(int i=; i<=n; i++)

        {

            s[*i]='#';

            s[*i-]=str[i-];

        }

        manacher(*n);

        memset(c,,sizeof(c));

        for(int i=; i<=*n; i++)

        {

            int ori;

            if(i%==) ori = i/+;

            else ori = (i+)/;

            int ori1 = (i+p[i]-)/+;

            if(ori1<=ori) continue;

            update(ori,);

            update(ori1,-);

        }

        memset(l,,sizeof(l));

        for(int i=; i<=n; i++)

        {

            l[i] = l[i-]+getsum(i);

        }

        reverse(s,s+*n+);

        manacher(*n);

        memset(c,,sizeof(c));

        for(int i=; i<=*n; i++)

        {

            int ori;

            if(i%==) ori = i/+;

            else ori = (i+)/;

            int ori1 = (i+p[i]-)/+;

            if(ori1<=ori) continue;

            update(ori,);

            update(ori1,-);

        }

        LL ans = ;

        for(int i=; i<=n; i++)

        {

            ans += getsum(i)*l[n-i];

        }

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

    }

    return ;

}

巴特西

hdu 5157(树状数组+Manacher)

Harry and magic string

最新文章

热门文章