题目大意：
给个字符串X，要把X分成两段T1,T2，每个字母都有一个对应的价值，如果T1，，T2是回文串（从左往右或者从右往左读，都一样），那么他们就会有一个价值，这个价值是这个串的所有字母价值之和，如果不是回文串，那么这串价值就为0。问最多能获得多少价值？
思路：
把字符串X逆序后得到字符串Y
让X去匹配Y ，匹配的长度满足extend[i] + i == len, len=|X|. 的那么X与y的匹配部分是回文串，这不难理解，画图即可
总复杂度是O（n），由于这是求前缀和后缀的回文，用拓展KMP可以方便解决
由于是回文串问题，用Manacher算法可以大显身手，算法复杂度也是O(n)
拓展KMP:
//124MS 11860K#include<cstdio>#include<cstring>#include<cstdio>#include<algorithm>#define N 500100using namespace std;char a[N],b[N];int value[30];int sum[N];int next1[N],extend1[N];int next2[N],extend2[N];void pre_EKMP(char x[],int m,int next[]){next[0]=m;int j=0;while(j+1<m&&x[j]==x[j+1]) j++;next[1]=j;int k = 1;for(int i=2;i<m;i++){int p=next[k]+k-1;int L=next[i-k];if(i+L-1<p) next[i]=L;else{j=max(0,p-i+1);while(i+j<m&&x[i+j]==x[j]) j++;next[i]=j;k=i;}}}void EKMP(char x[],int m,char y[],int n,int next[],int extend[]){pre_EKMP(x,m,next);int j=0;while(j<m&&j<n && y[j]==x[j]) j++;extend[0]=j;int k=0;for(int i=1;i<n;i++){int p=extend[k]+k-1;int L=next[i-k];if(i+L<p+1) extend[i]=L;else {j=max(0,p-i+1);while(j<m&&i+j<n&&y[i+j]==x[j]) j++;extend[i]=j;k=i;}}}int main(){int T;scanf("%d",&T);while(T–){for(int i=0;i<26;i++) scanf("%d",&value[i]);scanf("%s",a);int len=strlen(a);sum[0]=value[a[0]-'a' ];for(int i=1;i<len;i++)sum[i]=sum[i-1]+value[a[i]-'a' ];for(int i=0;i<len;i++) b[i]=a[len-i-1];b[len]=0;EKMP(a,len,b,len,next1,extend1); //求前缀EKMP(b,len,a,len,next2,extend2);int ans=-1;for(int i=1;i<len;i++){int tmp=0;int j=len-i;if(i+extend1[i]==len) tmp+=sum[len-i-1];if(j+extend2[j]==len) tmp+=(sum[len-1]-sum[len-i-1 ]);if(tmp>ans) ans=tmp;}printf("%d\n",ans);}}
Manacher ：
//156MS 9412K#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define N 500100using namespace std;char Ma[N<<1],s[N];int Mp[N<<1],sum[N];bool pref[N],suff[N];int value[30];void Manacher(int len){memset(pref,0,sizeof(pref));memset(suff,0,sizeof(suff));int l=0;Ma[l++]='$';Ma[l++]='#';for(int i=0;s[i];i++){Ma[l++]=s[i];Ma[l++]='#';}Ma[l]=0;int mx=0,mid=0;for(int i=1;i<l;i++){Mp[i] = mx>i? min(Mp[2*mid-i],mx-i):1;while(Ma[i-Mp[i] ]==Ma[i+Mp[i] ]) Mp[i]++;if(i+Mp[i]>mx){mid=i;mx=i+Mp[i];}if(i-Mp[i]==0) /*&&Mp[i]>1 也可在条件上加上这句避免数组下标是负值，不加也ac，遇过几次这种情况了…*/pref[Mp[i]-2]=true;if(i+Mp[i]==l) /*&&Mp[i]>1*/suff[len-(Mp[i]-1)]=true;}}int main(){int T;scanf("%d",&T);while(T–){for(int i=0;i<26;i++) scanf("%d",&value[i]);scanf("%s",s);sum[0]=value[s[0]-'a'];for(int i=1;s[i];i++) sum[i]=(sum[i-1]+value[s[i]-'a' ]);int len=strlen(s);Manacher(len);int ans=-1;for(int i=0;i<len-1;i++){int tmp=0;if(pref[i]) tmp+=sum[i];if(suff[i+1]) tmp+=(sum[len-1]-sum[i]);if(tmp>ans) ans=tmp;}printf("%d\n",ans);}return 0;}
一错再错，把握正确的方向，
