首页 > 代码库 > hdu 3948 The Number of Palindromes

hdu 3948 The Number of Palindromes

2024-10-01 21:17:02   219人阅读

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
3
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 38using namespace std;const int MOD1=300137;const int MOD2=17707;const int MOD3=1e9+7;const int MOD4=1e9+9;char s[200011],a[100011];int p[200011],len,l,ans;int f1[200011],g1[200011];int f2[200011],g2[200011];int front1[MOD1+1],front2[MOD2+1];int to1[300100],to2[300100];int nxt1[300100],nxt2[300100];int tot1,tot2;void manacher(){    memset(p,0,sizeof(p));    int pos=0,id=0,x;    for(int i=1;i<=len;i++)    {        if(i<pos) x=min(p[2*id-i],pos-i);        else x=1;        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-1]*g1[r-l+1]%MOD3;    return (b-a+MOD3)%MOD3;}int get_hash2(int l,int r){    int a=f2[r];    int b=1ll*f2[l-1]*g2[r-l+1]%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>=1;i--)    {        int hash1=get_hash1(pos-i+1,pos+i-1);        int hash2=get_hash2(pos-i+1,pos+i-1);        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=0;    memset(front1,0,sizeof(front1));    memset(front2,0,sizeof(front2));    memset(f1,0,sizeof(f1));    memset(f2,0,sizeof(f2));    g1[0]=1;    for(int i=1;i<=len;i++) g1[i]=1ll*g1[i-1]*D1%MOD3;    f1[0]=s[0];    for(int i=1;i<=len;i++) f1[i]=(1LL*f1[i-1]*D1+s[i]-‘0‘)%MOD3;    g2[0]=1;    for(int i=1;i<=len;i++) g2[i]=1ll*g2[i-1]*D2%MOD4;    f2[0]=s[0];    for(int i=1;i<=len;i++) f2[i]=(1LL*f2[i-1]*D2+s[i]-‘0‘)%MOD4;}int main(){    int t;    scanf("%d",&t);    for(int tt=1;tt<=t;tt++)    {        scanf("%s",a);        s[len=0]=‘!‘;        l=strlen(a);        for(int i=0;i<l;i++)         {            s[++len]=‘#‘;            s[++len]=a[i];        }        s[++len]=‘#‘;        s[len+1]=‘&‘;        pre();        manacher();        for(int i=1;i<=len;i++)           cal(i,p[i]);        printf("Case #%d: %d\n",tt,ans/2);    }}

 

hdu 3948 The Number of Palindromes


联系
我们