首页 > 代码库 > HDU 3613 Best Reward（扩展KMP）
HDU 3613 Best Reward（扩展KMP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=3613
【题目大意】
一个字符串的价值定义为，当它是一个回文串的时候，价值为每个字符的价值的和，如果不是回文串，价值为0，现在给出每种字符的价值。给出一个字符串，要求将其划分为两个子串，要求两个子串的价值和最大。
【题解】
求出字符串S的反串T，以T为模板跑一遍S的exkmp就能得到S的后缀是否为回文串的信息，同理以S为模板跑一遍T就可以得到S的前缀是否是回文串的信息，枚举每个断点，取最大值即可。
【代码】
#include <cstdio>#include <cstring> using namespace std;const int N=500010;int len,LCP[N],ex1[N],ex2[N],a[N],s[N];char S[N],T[N];void getLCP(char *T){ int i,len=strlen(T); LCP[0]=len; for(i=0;i<len-1&&T[i]==T[i+1];i++); LCP[1]=i; int a=1; for(int k=2;k<len;k++){ int p=a+LCP[a]-1,L=LCP[k-a]; if((k-1)+L>=p){ int j=(p-k+1)>0?(p-k+1):0; while(k+j<len&&T[k+j]==T[j])j++; LCP[k]=j,a=k; }else LCP[k]=L; } }void exkmp(char *S,char *T,int *extend){ memset(LCP,0,sizeof(LCP)); getLCP(T); int Slen=strlen(S),Tlen=strlen(T),a=0; int MinLen=Slen>Tlen?Tlen:Slen; 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=LCP[k-a]; if((k-1)+L>=p){ int j=(p-k+1)>0?(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; }}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]; }int Cas;int main(){ scanf("%d",&Cas); while(Cas--){ for(int i=0;i<26;i++)scanf("%d",&a[i]); scanf("%s",S);len=strlen(S); for(int i=0;S[i];i++)s[i+1]=s[i]+a[S[i]-‘a‘]; revcpy(S,T,len); exkmp(S,T,ex2); exkmp(T,S,ex1); int ans=-1e9; for(int i=0;i<len;i++){ if(i&&ex1[i]+i==len){ int j=ex1[i],tmp=s[j]; if(ex2[j]+j==len)tmp+=s[len]-s[j]; if(tmp>ans)ans=tmp; }else{ int j=i+1,tmp=0; if(ex2[j]+j==len)tmp+=s[len]-s[j]; if(tmp>ans)ans=tmp; } }printf("%d\n",ans); }return 0;}HDU 3613 Best Reward（扩展KMP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。