题目来源：HDU 3613 Best Reward

题意：每一个字母相应一个权值 将给你的字符串分成两部分 假设一部分是回文 这部分的值就是每一个字母的权值之和 求一种分法使得2部分的和最大

思路：考虑扩展KMP 输出a串 得到a的反串b 求出f[0]和f[1] 和 extend[0]和extend[1] 正反求2次

枚举位置i 分成2部分0到i-1 和i到n-1 由于分成的2部分必须组成原字符串 就是不能多也不能少

那么推断i+extend[i]是否等于n 等于说明i到n-1这个部分是回文串 sum1 为这部分的值 假设这部分不是回文sum1 = 0

推断0到i-1是不是回文 将a和b翻转 那么就和推断i到n-1是一样的  所以上面正反求了2次 sum2 为这部分的值 假设这部分不是回文sum2 = 0

去sum1+sum2的最大值 另外字符串的值能够递推求得

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 500010;

int f[2][maxn], ex[2][maxn];

char a[maxn], b[maxn];

int id[26], dp[2][maxn];

void getFail(char* s, int id, int n)

{

	int k = 1, p = 0;

	while(p+1 < n && s[p] == s[p+1])

		p++;

	f[id][0] = n;

	f[id][1] = p;

	for(int i = 2; i < n; i++)

	{

		int l = f[id][i-k];

		int p = f[id][k]+k-1;

		if(i+l-1 < p)

			f[id][i] = l;

		else

		{

			int j = p-i+1;

			if(j < 0)

				j = 0;

			while(i+j < n && s[i+j] == s[j])

				j++;

			f[id][i] = j;

			k = i;

		}

	}

}

void getEx(char* s, char* t, int id, int n)

{

	int k = 0, p = 0;

	while(p < n && s[p] == t[p])

		p++;

	ex[id][0] = p;

	for(int i = 1; i < n; i++)

	{

		int l = f[id^1][i-k];

		int p = ex[id][k]+k-1;

		if(i+l-1 < p)

			ex[id][i] = l;

		else

		{

			int j = p-i+1;

			if(j < 0)

				j = 0;

			while(i+j < n && s[i+j] == t[j])

				j++;

			ex[id][i] = j;

			k = i;

		}

	}

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		for(int i = 0; i < 26; i++)

			scanf("%d", &id[i]);

		scanf("%s", a);

		int n = strlen(a);

		for(int i = 0; i < n; i++)

		{

			b[i] = a[n-i-1];

			if(i)

				dp[0][i] = id[a[i]-'a'] + dp[0][i-1];

			else

				dp[0][i] = id[a[i]-'a'];

		}

		for(int i = 0; i < n; i++)

		{

			if(i)

				dp[1][i] = dp[1][i-1] + id[b[i]-'a'];

			else

				dp[1][i] = id[b[i]-'a'];

		}

		getFail(a, 0, n);

		getFail(b, 1, n);

		getEx(a, b, 0, n);

		getEx(b, a, 1, n);

		int ans = 0;

		for(int i = 1; i < n; i++)

		{

			int sum1 = 0, sum2 = 0;

			if(i+ex[0][i] == n)

				sum1 = dp[1][ex[0][i]-1];

			int j = n-i;

			if(j+ex[1][j] == n)

				sum2 = dp[0][ex[1][j]-1];

			ans = max(ans, sum1+sum2);

			//printf("%d %d\n", ex[0][i], ex[1][i]);

		}

		printf("%d\n", ans);

	}

	return 0;

}