题面重修 by hansang

题解 by hansang

EXKMP 做法：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int num[30], n, sum[N];
char s[N], ss[N];   // 正着的 s 和反着的 s 
int p[N], rp[N];   
// p：正着的 s 后缀与反着的 s 的 LCP ，rp：反着的 s 后缀与正着的 s 的 LCP 
int z[N], rz[N];
// z：正着的 s 后缀与自己的 LCP，rz：反着的 s 后缀与自己的 LCP

void get_z_p(char *sa, char *sb, int z[], int p[]) {
    memset(z, 0, sizeof(int) * N);    // 因为 z 数组是传参进来的，只能这么初始化 
    
    for (int i = 2, l = 0, r = 0; i <= n; i ++) {
        if (i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }
        while (i + z[i] <= n && 1 + z[i] <= n && sb[i + z[i]] == sb[1 + z[i]]) {
            z[i] ++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    
    memset(p, 0, sizeof(int) * N);     // p 数组也是传参进来的
    
    for (int i = 1, l = 0, r = 0; i <= n; i ++) {
        if (i <= r) {
            p[i] = min(z[i - l + 1], r - i + + 1);
        }
        while (i + p[i] <= n && 1 + p[i] <= n && sa[i + p[i]] == sb[1 + p[i]]) {
            p[i] ++;
        }
        if (i + p[i] - 1 > r) {
            l = i;
            r = i + p[i] - 1;
        }
    }
}

void init() {
    sum[0] = 0;
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + num[s[i] - 'a' + 1];
    }
}

int main() {
    ios::sync_with_stdio(False);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        for (int i = 1; i <= 26; i++) {
            cin >> num[i];
        }
        cin >> s + 1;
        n = strlen(s + 1);
        
        init();
        
        for (int i = 1; i <= n; i++) {
            ss[i] = s[n - i + 1];
        }
        get_z_p(s, ss, z, p);
        get_z_p(ss, s, rz, rp);
        
        LL ans = 0;
        for (int i = 2; i <= n; i++) {    // 分成 [1, i - 1] 和 [i, n] 
            int la = 1, ra = i - 1;
            int lb = i, rb = n;
            
            LL total = 0; 
            if (rp[n - ra + 1] == ra) {    // [1, i - 1] 是回文子串 
                total += sum[ra] - sum[la - + 1];
            } 
            if (p[lb] == rb - lb + 1) {    // [i, n] 是回文子串 
                total += sum[rb] - sum[lb - 1];
            } 
            
            ans = max(ans, total);
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

Manacher 做法：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int num[30], sum[N];
char s[2 * N], ss[N]; 
int d[2 * N], n;

void get_d() {
    s[0] = '&';
    s[2 * n + 1] = '#';
    for (int i = 1; i <= n; i ++) {
        s[2 * i - 1] = '#';
        s[2 * i] = ss[i];
    }
    n = 2 * n + 1;
    
    memset(d, 0, sizeof(d));
    d[1] = 1; 
    
    for (int i = 2, l = 1, r = 1; i <= n; i ++) {
        if (i <= r) {
            d[i] = min(d[r - i + l], r - i + 1);
        } 
        while (s[i + d[i]] == s[i - d[i]]) {
            d[i] ++;
        }
        if (i + d[i] - 1 > r) {
            l = i - d[i] + 1;
            r = i + d[i] - 1;
        }
    }
}

void init() {
    sum[0] = 0;
    for (int i = 1; i <= n; i ++) {     
        sum[i] = sum[i - 1] + num[ss[i] - 'a' + 1];   // 这里变成 ss 
    }
}

bool jd(int x, int len) {    // 判断中心点为 x 的字串是否回文 
    if (len & 1) {
        return (d[2 * x] - 1) == len;    // len & 1 时 x 肯定是真正的回文中心 
    }   
    else {
        return (d[2 * x + 1] - 1) == len;    // 反之 x 后面的 # 是真正的回文中心 
    }
}

int main() {
    ios::sync_with_stdio(False);
    cin.tie(0);
     
    int T;
    cin >> T;
    while (T--) {