题意:给你每个字符的价值，再给你一个字符串,要你把这个字符串分成两段,并使得被分开的两段价值和最大.一个串如果是回文,那么它的价值就是所有字符的价值和,否则价值为0。
解法1(exKMP):s串为原串，我们让t串等于s串的reverse。因为回文串有个性质就是reverse前后样子不变，所以我们可以根据这个性质来对每个位置i同时用2次exkmp(对象相反)，把当前位置i的前和后是否有回文串找出，并用前缀和来求其价值，每次操作更新当前i的最大价值。
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const int mod=1e9+7; const int maxn=5e5+5; int extend1[maxn],extend2[maxn],net[maxn]; char s[maxn],t[maxn]; void getnext(char *t){ memset(net,0,sizeof(net)); int len=strlen(t); net[0]=len; int a=1,p; while(a<len&&t[a]==t[a-1]) a++; net[1]=a-1; a=1; for(int i=2;i<len;i++){ p=a+net[a]-1; if((i-1)+net[i-a]<p) net[i]=net[i-a]; else{ int j=(p-i+1)>0 ? (p-i+1):0; while(i+j<len&&t[i+j]==t[j]) j++; net[i]=j; a=i; } } } void exkmp(char *s,char *t,int *extend){ getnext(t); int a,p; int lens=strlen(s); int lent=strlen(t); a=p=0; int len=min(strlen(s),strlen(t)); while(p<len&&t[p]==s[p]) p++; extend[0]=p; for(int i=1;i<lens;i++){ p=a+extend[a]-1; if((i-1)+net[i-a]<p) extend[i]=net[i-a]; else{ int j=(p-i+1)>0 ? (p-i+1):0; while(j<lent&&i+j<lens&&s[i+j]==t[j]) j++; extend[i]=j; a=i; } } } int w[maxn],sum[maxn]; int main(){ int T;cin>>T; while(T--){ map<char,int>mp; rep(i,0,25){ int x;cin>>x; mp['a'+i]=x; } scanf("%s",s); int n=strlen(s); for(int i=0;i<n;i++){ t[n-i-1]=s[i]; if(i==0) sum[i]=mp[s[i]]; else sum[i]=sum[i-1]+mp[s[i]]; } exkmp(t,s,extend1); exkmp(s,t,extend2); int ans=-INF; for(int i=1;i<n;i++){ int sc=0; if(extend1[n-i]+n-i==n){ sc+=sum[i-1]; } if(extend2[i]+i==n){ sc+=sum[n-1]-sum[i-1]; } ans=max(ans,sc); } cout<<ans<<endl; } }
解法2(Manacher算法):就是遍历每个#位置(从第2个#到导数第2个#)作为端点的左右最大回文串，判断左右回文串长度是否等于到边界的长度，如果是的话，就利用前缀和进行对当前轮sc加，不断更新最后取最大max(马拉车记得数组开2倍哦)
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const int mod=1e9+7; const int maxn=5e5+5; char s[maxn]; char str[maxn<<1]; int p[maxn<<1],len; int init(){ int len=strlen(s); str[0]='@',str[1]='#'; int j=2; for(int i=0;i<len;i++) str[j++]=s[i],str[j++]='#'; str[j]=' '; return j; } int R[maxn<<1],L[maxn<<1]; void manacher(){ len=init();int mx=0,id=0; for (int i=1;i<len;i++) { if(i<mx) p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(str[i+p[i]]==str[i-p[i]]) p[i]++; if(p[i]+i>mx) mx=p[i]+i,id=i; R[i+p[i]-1]=max(R[i+p[i]-1],p[i]-1); L[i-p[i]+1]=max(L[i-p[i]+1],p[i]-1); } } int sum[maxn<<1]; int main(){ int T;scanf("%d",&T); while(T--){ unordered_map<char,int>mp; rep(i,0,25){ int x;scanf("%d",&x); mp['a'+i]=x; } scanf("%s",s); int n=strlen(s); manacher(); mp['@']=mp['#']=0; for(int i=0;i<len;i++){ if(i==0) sum[i]=mp[str[i]]; else sum[i]=sum[i-1]+mp[str[i]]; } for(int i=len-1;i>=1;i-=2) R[i]=max(R[i],R[i+2]-2); for(int i=3;i<=len-1;i+=2) L[i]=max(L[i],L[i-2]-2); int ans=-INF; for(int i=3;i<=len-3;i+=2){ int sc=0; if(R[i]==(i-1)/2) sc+=sum[i]; if(L[i]==n-(i-1)/2) sc+=sum[len-1]-sum[i]; ans=max(ans,sc); } printf("%d ",ans); } }