原题

source:2010 ACM-ICPC Multi-University Training Contest（18）——Host by TJU

题目大意：

题目首先给出了二十六个字符的价值，有正有负。对于一个串的价值，如果这个串是一个回文串那么他的价值就是所有回文串中所有字母的和，如果不是回文串那么价值为0。题中给出了一个串，问我们的是如果我们把串劈成两半，所有可能的情况中左右串加起来价值最大是多少。

解题思路：

这里我们使用扩展KMP来求解回文串，首先我们复制输入的原串并将它置反。利用扩展KMP算法分别以原串为主串，反串为模式串得到extend1，以反串为主串，原串为模式串得到extend2。

利用这两个数组我们发现：如果extend1[i]+i==len(S)，那么我们就可以知道原串中从第i位开始到结束为止是个回文串。

同理利用extend2数组来判断前i个字符是否是回文串

同时我们先预处理一个sum数组，用于记录原串中前i个字符的价值和是多少方便后面计算。

于是我们就可以用线性复杂度枚举切割的位置，得到其价值最大值

扩展KMP算法详解请参见博客：
https://roarboil.github.io/2019/11/21/extendkmp/

AC代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 500010
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int exnxt[maxn];
int extend1[maxn];
int extend2[maxn];
char S[maxn];
char T[maxn];
void ex_GetNext()
{
    int m = strlen(T);
    int a = 0, p = 0;
    exnxt[0] = m;
    
    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + exnxt[i - a] >= p)
        {
            if (i >= p)
                p = i;
            
            while (p < m && T[p] == T[p - i])
                p++;
            
            exnxt[i] = p - i;
            a = i;
        }
        else
            exnxt[i] = exnxt[i - a];
    }
}

/* 求解 extend[] */
void GetExtend1()
{
    int a = 0, p = 0;
    int n = strlen(S);
    int m = strlen(T);
    ex_GetNext();
    
    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + exnxt[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;

            while (p < n && p - i < m && S[p] == T[p - i])
                p++;
            
            extend1[i] = p - i;
            a = i;
        }
        else
            extend1[i] = exnxt[i - a];
    }
}
void GetExtend2()
{
    int a = 0, p = 0;
    int m = strlen(S);
    int n = strlen(T);
    ex_GetNext();
    
    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + exnxt[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;
            
            while (p < n && p - i < m && T[p] == S[p - i])
                p++;
            
            extend2[i] = p - i;
            a = i;
        }
        else
            extend2[i] = exnxt[i - a];
    }
}
int v[30];
int sum[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        rep(i, 26)
        {
            scanf("%d",&v[i]);
        }
        scanf("%s",S);
        int lens = strlen(S);
        sum[0] = v[S[0]-'a'];
        rep(i,lens)
        {
            T[lens-i-1] = S[i];
            if (i != 0)
                sum[i] = v[S[i]-'a'] + sum[i-1];
        }
        T[lens] = 0;
        GetExtend1();
        GetExtend2();
        int ans = max(v[S[0]-'a'] , v[S[lens-1]-'a']);
        repr(i,1,lens)
        {
            int temp = 0;
            if (extend2[lens - i] + lens -i ==lens)
                temp += sum[i-1];
            if (extend1[i] + i == lens)
                temp += sum[lens-1] - sum[i-1];
            ans = max(ans, temp);
        }
        cout << ans << endl;
    }
    return 0;
}