链接:
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
4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **数学应用**:组合数学、数论(质因数分解、模运算、欧几里得算法等)、概率论等。 6. **编码技巧**:IO优化(如scanf/printf代替cin/...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
字符串处理是 ACM HDU 题目分类中的一大类,例如,1020 简单的字符串处理;1048 简单字符串处理;1062 简单字符串处理;1073 字符串处理 等等。 其他 除了以上分类外,ACM HDU 题目分类还包括其他一些分类,例如,...
3. **字符串处理**:杭电ACM中的题目可能涉及到字符串匹配(KMP算法、Boyer-Moore算法)、编码解码、模式查找等问题,熟悉字符串操作是必备技能。 4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
5. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串的模式匹配和操作。2151-2200号题目可能需要处理字符串数据,如计算最长重复子串或检查回文串。 6. **数学与计算几何**:2201-2250号...
6. **字符串处理**:模式匹配、KMP算法、Manacher's Algorithm等。 7. **模拟法**:直接按照题目描述进行程序模拟,解决一些逻辑性较强的问题。 学习和理解ACM HDU的题解,不仅可以提升编程能力,还能帮助我们理解...
6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等。 通过分析和理解这些代码,你可以提升自己的算法思维,学习如何高效地解决问题,这对于参加ACM竞赛或者日常的编程工作都非常有益。同时,也可以借鉴代码...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
5. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法用于字符串匹配,Z算法、Manacher算法处理回文串问题。这些在文本处理、模式查找题目中必不可少。 6. **数据结构**:线段树、斐波那契堆、平衡树(AVL...
3. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串操作和模式匹配技巧。 4. **数学知识**:组合数学、离散数学、数论等,许多竞赛题目需要运用到这些数学原理。 5. **优化技巧**:...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
在竞赛编程中,字符串问题可能涉及到KMP算法、Manacher's Algorithm(曼哈顿算法)或者Rabin-Karp滚动哈希等技术,用于高效地处理字符串的匹配和操作。 4. **动态规划(DP)**:动态规划是一种解决问题的系统方法,...
"yfndq2"可能是一个字符串处理或模式匹配的问题,可能用到了KMP、Boyer-Moore等字符串匹配算法。而"flymaidou"可能是涉及数值计算或数学推理的题目,需要理解和应用特定的数学公式或方法。 在学习这些源代码时,...
hdu2101AC代码