hdu 3948 The Number of Palindromes

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

The Number of Palindromes

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
http://acm.hdu.edu.cn/showproblem.php?pid=3948

Problem Description

Now, you are given a string S. We want to know how many
distinct substring of S which is palindrome.

Input

The first line of the input contains a single integer
T(T<=20), which indicates number of test cases.
Each test case consists of
a string S, whose length is less than 100000 and only contains lowercase
letters.

Output

For every test case, you should output "Case #k:" first
in a single line, where k indicates the case number and starts at 1. Then output
the number of distinct substring of S which is palindrome.

Sample Input

aaaa

abab

abcd

Sample Output

Case #1: 4

Case #2: 4

Case #3: 4

Source

2011
Multi-University Training Contest 11 - Host by UESTC

Recommend

xubiao | We have carefully selected several similar
problems for you: 3946 3947 3949 3945 3944

题意：统计不同回文串的个数

首先对原串跑一遍manacher算法，处理出最长回文半径

然后枚举每一个位置

从最长的回文串开始一点一点儿往里索，hash判断这个字符串是否出现过

如果出现过，那么比它更短的肯定也出现过，结束本位置的查找，到下一个位置

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define D1 28

#define D2 38

using namespace std;

const int MOD1=;

const int MOD2=;

const int MOD3=1e9+;

const int MOD4=1e9+;

char s[],a[];

int p[],len,l,ans;

int f1[],g1[];

int f2[],g2[];

int front1[MOD1+],front2[MOD2+];

int to1[],to2[];

int nxt1[],nxt2[];

int tot1,tot2;

void manacher()

{

    memset(p,,sizeof(p));

    int pos=,id=,x;

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

    {

        if(i<pos) x=min(p[*id-i],pos-i);

        else x=;

        while(s[i+x]==s[i-x])    x++;

        if(i+x>pos) { pos=i+x; id=i; }

        p[i]=x;

    }

}

int get_hash1(int l,int r)

{

    int a=f1[r];

    int b=1ll*f1[l-]*g1[r-l+]%MOD3;

    return (b-a+MOD3)%MOD3;

}

int get_hash2(int l,int r)

{

    int a=f2[r];

    int b=1ll*f2[l-]*g2[r-l+]%MOD4;

    return (b-a+MOD4)%MOD4;

}

void add1(int u,int v)

{

    to1[++tot1]=v; nxt1[tot1]=front1[u]; front1[u]=tot1;

}

void add2(int u,int v)

{

    to2[++tot2]=v; nxt2[tot2]=front2[u]; front2[u]=tot2;

}

bool find1(int u,int v)

{

    for(int i=front1[u];i;i=nxt1[i])

     if(to1[i]==v) return true;

    return false;

}

bool find2(int u,int v)

{

    for(int i=front2[u];i;i=nxt2[i])

     if(to2[i]==v) return true;

    return false;

}

void cal(int pos,int len)

{

    for(int i=len;i>=;i--)

    {

        int hash1=get_hash1(pos-i+,pos+i-);

        int hash2=get_hash2(pos-i+,pos+i-);

        int t1=hash1%MOD1,t2=hash2%MOD2;

        if(!(find1(t1,hash1)&&find2(t2,hash2)))

        {

            ans++;

            add1(t1,hash1);

            add2(t2,hash2);

        }

        else return;

    }

}

void pre()

{

    ans=tot1=tot2=;

    memset(front1,,sizeof(front1));

    memset(front2,,sizeof(front2));

    memset(f1,,sizeof(f1));

    memset(f2,,sizeof(f2));

    g1[]=;

    for(int i=;i<=len;i++) g1[i]=1ll*g1[i-]*D1%MOD3;

    f1[]=s[];

    for(int i=;i<=len;i++) f1[i]=(1LL*f1[i-]*D1+s[i]-'')%MOD3;

    g2[]=;

    for(int i=;i<=len;i++) g2[i]=1ll*g2[i-]*D2%MOD4;

    f2[]=s[];

    for(int i=;i<=len;i++) f2[i]=(1LL*f2[i-]*D2+s[i]-'')%MOD4;

}

int main()

{

    int t;

    scanf("%d",&t);

    for(int tt=;tt<=t;tt++)

    {

        scanf("%s",a);

        s[len=]='!';

        l=strlen(a);

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

        {

            s[++len]='#';

            s[++len]=a[i];

        }

        s[++len]='#';

        s[len+]='&';

        pre();

        manacher();

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

           cal(i,p[i]);

        printf("Case #%d: %d\n",tt,ans/);

    }

}