首页 > 代码库 > hdu 3948 The Number of Palindromes
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.
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。