链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3613
题目大意:
给个字符串S,要把S分成两段T1,T2,每个字母都有一个对应的价值,如果T1,T2是回文串(从左往右或者从右往左读,都一样),那么他们就会有一个价值,这个价值是这个串的所有字母价值之和,如果不是回文串,那么这串价值就为0。问最多能获得多少价值?
分析与总结:
观察字符串S,以及由S逆序得到的字符串T:
S:acacac
T:cacaca
如果要求S的前缀回文,只需要用拓展KMP算法让S去匹配T,求出所有T的后缀T【i】与S前缀的公共串长度,保存在extend数组中,得到:0, 5, 0, 3, 0, 1
其中extend中的位置1,3,5是有公共串的,并且匹配的长度满足extend[i] + i == len, len=|S|.
并且S这几个长度的前缀都是回文串!
所以,对于我们只需要枚举扫描一遍extend数组,扫描到的当前位置之前为前半部分T1, 然后用根据extend数组可以判断T1是否是回文。那后半部分T2呢? 刚才是用S去匹配T, 如果要求后缀,只需要用T去匹配S,再得到一个数组extend2即可,根据这个extend2判断后半部分T2是否是回文。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 500005;
char S[MAXN];
char T[MAXN];
int f[MAXN];
int extend1[MAXN];
int extend2[MAXN];
int val[30];
int sum[MAXN];
void revcpy(char* s,char* t,int len){
memset(t, 0, sizeof(t));
for(int i=0, k=len-1; i<len; ++i,--k)
t[i] = s[k];
}
void getNext(char* T,int* next){
int len=strlen(T), a=0;
next[0]=len;
while(a<len-1 && T[a]==T[a+1]) ++a;
next[1]=a;
a=1;
for(int k=2; k<len; ++k){
int p=a+next[a]-1, L=next[k-a];
if(k+L-1>=p){
int j=max(p-k+1,0);
while(k+j<len && T[k+j]==T[j])++j;
next[k]=j;
a=k;
}
else
next[k]=L;
}
}
void EKMP(char* S,char* T,int* next, int* extend){
getNext(T,next);
int slen=strlen(S), tlen=strlen(T), a=0;
int minlen=min(slen,tlen);
while(a<minlen && S[a]==T[a])++a;
extend[0] = a;
a=0;
for(int k=1; k<slen; ++k){
int p=a+extend[a]-1, L=next[k-a];
if(k-1+L >= p){
int j=max(p-k+1,0);
while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;
extend[k] = j;
a=k;
}
else
extend[k] = L;
}
}
int main(){
int nCase;
scanf("%d",&nCase);
while(nCase--){
for(int i=0; i<26; ++i)
scanf("%d",&val[i]);
scanf("%s",S);
memset(sum, 0, sizeof(sum));
for(int i=0; S[i]; ++i){
sum[i+1] = val[S[i]-'a']+sum[i];
}
int len=strlen(S);
revcpy(S,T,strlen(S));
EKMP(S,T,f,extend2);
EKMP(T,S,f,extend1);
int maxx=-1000000000;
for(int i=0; i<len; ++i){
if(i && extend1[i]+i==len){ //如果半部分是回文
int pos=extend1[i];
int tmp=sum[pos];
if(extend2[pos]+pos==len){ // 看后半部分是否也是回文
tmp += sum[len]-sum[pos];
}
if(tmp > maxx)
maxx=tmp;
}
else{ //如果前半部分不是回文,看后半不部分
int pos=i+1,tmp=0;
if(extend2[pos]+pos==len){
tmp += sum[len]-sum[pos];
}
if(tmp > maxx)
maxx=tmp;
}
}
printf("%d\n",maxx);
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码