题目链接:http://codeforces.com/contest/7/problem/D
题意:
“等级”的定义是,
每个串(包括空串)的等级至少为0,
若一个长度为len的前缀是回文串,
且它的长度为floor(len/2)的前缀和后缀的“等级”为k,
则它的等级是k+1。
求一个字符串所有前缀的“等级”和。
算法:
我是用manacher算法求的回文串。
manacher算法的介绍很多,比如这个:http://twocoldzcainiao.sinaapp.com/?p=238
简单来说,manacher算法是把原字符串映射成一个'*'和字符交替的新字符串,
从而把所有的回文串映射成新串中一个长度为奇数的字符串。
因此可以在O(n)时间内处理出以每个字符为中心可以延伸出多长的回文串。
对于本题,
对于每一个前缀,直接找出它的中心,
注意,这个中心可能是字符也可能是"*",
通过这个中心延伸的回文串长度判断这个前缀是不是回文串。
如果是的话,找到这个回文串的中心字符,也就是s[(i-1)/2],就可以递推求出等级。
当然这道题也可以用hash做,
推荐一个写的比较清爽的代码:
http://codeforces.com/contest/7/submission/3995867
不过据专业人士称这个代码的质数取的太小。。
代码如下:
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<climits> #include<cmath> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<set> #include<map> #define INF 0x3f3f3f3f using namespace std; const int MAXN=5100000; char s[MAXN<<1]; int p[MAXN<<1]; int rank[MAXN]; int main() { while(~scanf("%s",s)) { int n=strlen(s); s[2*n+2]='\0'; for(int i=n-1; i>=0; i--) { s[2*i+2]=s[i]; s[2*i+3]='*'; } s[0]='$'; s[1]='*'; memset(p,0,sizeof(p)); int maxn=0,maxi=0; long long ans=0LL; for(int i=1; i<2*n+2; i++) { p[i]=maxn>i?min(p[2*maxi-i],maxn-i):1; while(s[i+p[i]]==s[i-p[i]])p[i]++; if(maxn<i+p[i]) { maxn=i+p[i]; maxi=i; } } memset(rank,0,sizeof(rank)); for(int i=0; i<n; i++) { if(p[i+2]!=i+2) { rank[i]=0; } else { if(i) { rank[i]=rank[(i-1)/2]+1; } rank[i]=max(rank[i],1); } ans+=rank[i]; } printf("%I64d\n",ans); } return 0; }