基本思想就是暴力枚举分割处
没什么难的
关键是如何判断,分割后左边和右边是否是回文的
很简单的我们可以利用扩展kmp搞
当然也可以利用hash搞
随便搞
我这里用了扩展kmp
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 5e5+100; void getnext(char p[],int net[]) { register int a = 0;register int b = 0; int pn = strlen(p); net[0] = pn; for (register int i = 1;i < pn;++i) { if (i >= b || i + net[i - a] >= b) { if (i >= b) b = i; while (b < pn && p[b - i] == p[b]) ++b; net[i] = b - i; a = i; } else net[i] = net[i - a]; } } void getextend(char s[], char p[],int net[],int extend[]) { int a = 0;int b = 0; int pn = strlen(p);int sn = strlen(s); for (register int i = 0;i < sn;++i) { if (i >= b || i + net[i - a] >= b) { if (i >= b) b = i; while (b < sn && b - i < pn && p[b - i] == s[b]) ++b; extend[i] = b - i; a = i; } else extend[i] = net[i - a]; } } char s[max_n]; char s1[max_n]; int val[30]; int net1[max_n],net2[max_n],extend1[max_n],extend2[max_n]; int pre[max_n]; int main(){ int T;scanf("%d",&T); while (T--){ for (int i=0;i<26;++i)scanf("%d",&val[i]); scanf("%s",s);int n = strlen(s);s1[n]='\0'; for (int i=0;i<n;++i)s1[i]=s[n-i-1]; getnext(s,net1);getnext(s1,net2); getextend(s1,s,net1,extend1); getextend(s,s1,net2,extend2); pre[0]=val[s[0]-'a']; for (int i=1;i<n;++i)pre[i]=pre[i-1]+val[s[i]-'a']; int ans = 0; // for (int i=0;i<n;++i)printf("%d ",pre[i]);puts(""); // printf("%s\n",s1); for(int i=0;i<n-1;++i){ int res = 0; // printf("(%d,%d,%d);",i,extend1[n-i-1],extend2[i+1]); if (extend1[n-i-1]>=i+1)res+=pre[i]; if (extend2[i+1]>=n-i-1)res+=pre[n-1]-pre[i]; ans = max(ans,res); } printf("%d\n",ans); } }