Best Reward HDU - 3613

基本思想就是暴力枚举分割处
没什么难的

关键是如何判断，分割后左边和右边是否是回文的

很简单的我们可以利用扩展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);
    }
}