题意：
国王为了犒劳立下战功的大将军Li，决定奖给Li一串项链，这个项链一共包含26中珠子"a~z"，每种珠子都有
相应的价值（-100~100），当某个项链可以构成回文时，那么这个项链的价值就是每个珠子价值的加和，如果
构不成，那么这个项链的价值就为0；
求如何将国王奖赏的一串项链拆成价值加和最大的两串项链，求出这个最大价值。
题解：
本来我是在找有关拓展KMP的相关题目的，百度到一大牛的博客（“扩展KMP题目”），当做到第二个题目的时候，
思来想去，就是没找到其和拓展KMP的联系，然后，感觉可以用Manacher算法，刷刷刷撸了个Manacher的代码
提交，AC，所以，我暂且谈谈如何用Manacher算法解这道题；
①首先将项链串s[]预处理（了解Manacher算法就理解啥意思了）；
②准备一个数组sum[]，sum[ i ]:预处理后的数组中前 i 个字符对应的价值的加和，'#'当作0；
③使用Manacher算法求解出回文半径数组radius[]；
④假设从 i 位置切割项链，将项链分成[ 0,i ],[ i,len-1 ]两串，分别求解对应的总价值，令ans=max{从i位置分割的总价值}
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=5e5+; int val[];
char s[*maxn];
char temp[maxn];
int radius[*maxn];
int sum[*maxn];
void Trans()
{
int len=strlen(s);
strcpy(temp,s);
for(int i=;i < len;++i)
{
s[*i]='#';
s[*i+]=temp[i];
}
s[*len]='#';
s[*len+]='\0';
}
void Manacher()
{
mem(radius,);
int len=strlen(s);
int R=;
int K=;
radius[]=;
for(int i=;i < len;++i)
{
int cnt=;
if(i >= R)
{
while(i+cnt < len && i-cnt >= && s[i+cnt] == s[i-cnt])
cnt++;
radius[i]=cnt;
if(i+cnt- > R)
{
R=i+cnt-;
K=i;
}
}
else
{
int j=K-(i-K);
if(i+radius[j]- != R)
radius[i]=min(R-i+,radius[j]);
else
{
cnt=R-i+;
while(i-cnt >= && i+cnt < len && s[i-cnt] == s[i+cnt])
cnt++;
radius[i]=cnt;
if(i+cnt- > R)
{
R=i+cnt-;
K=i;
}
}
}
}
}
int Solve()
{
Trans();//预处理字符串s
Manacher(); int len=strlen(s);
sum[]=;
for(int i=;i < len;++i)//前缀和
sum[i]=sum[i-]+(s[i] == '#' ? :val[s[i]-'a']); int ans=-INF;
for(int i=;i < len-;i+=)
{
int cnt=;
int x=(i+)>>;//[0,i+1]的中点坐标
if(radius[x] == x+)//判断[0,i]是否构成回文子串
cnt += sum[i]; int y=(len+i)>>;//[i+1,len-1]的中点坐标
if(radius[y] == len-y)//判断[i+1,len-1]是否构成回文子串
cnt += sum[len-]-sum[i];
ans=max(ans,cnt);
}
return ans;
}
int main()
{
// freopen("C:/Users/hyacinthLJP/Desktop/stdin/contest","r",stdin);
int test;
scanf("%d",&test);
while(test--)
{
for(int i=;i < ;++i)
scanf("%d",val+i);
scanf("%s",s);
printf("%d\n",Solve());
}
return ;
}