HDU 3613 Best Reward(拓展KMP求前缀回文串)

题目大意：
给个字符串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是否是回文。

代码：
[cpp]
#include
#include
#include
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 t[i] = s[k];
}
void getNext(char* T,int* next){
int len=strlen(T), a=0;
next[0]=len;
while(a next[1]=a;
a=1;
for(int k=2; 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 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 extend[0] = a;
a=0;
for(int k=1; 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 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 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;
}