hdu3613

题解：

EX_KMP

网上似乎说kmp也可以，但是我交了一发代码没过

然后标记一下哪一些前缀和后缀会问

暴力枚举拆开了的位置

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=500005;
int v[30],n,nxt[N],match[N],exnxt[N],exmatch[N];
int L[N],R[N];
char s[N],t[N];
void EXKMP(char s[],char t[],int n,int m)
{
    exnxt[0]=m;
    for (int i=1,po=1;t[i];i++)
     {
        int P=po+exnxt[po];
        exnxt[i]=max(min(exnxt[i-po],P-i),0);
        while (i+exnxt[i]<m&&t[exnxt[i]]==t[i+exnxt[i]])exnxt[i]++;
        if (i+exnxt[i]>P) po=i;
     }
    for (int i=0,po=0;s[i];i++)
     {
        int P=po+exmatch[po];
        exmatch[i]=max(min(exnxt[i-po],P-i),0);
        while (exmatch[i]<m&&i+exmatch[i]<n&&t[exmatch[i]]==s[i+exmatch[i]])exmatch[i]++;
        if (i+exmatch[i]>P) po=i;
     }
}
int main()
{
    int T; 
    scanf("%d",&T);
    while (T--)
     {
         memset(exmatch,0,sizeof exmatch);
        for (int i=0;i<26;i++) scanf("%d",&v[i]);
        scanf("%s",&s);
        n=strlen(s);
        if (n<2)
         {
            puts("0");
            continue;
         }
        for (int i=0;i<n;i++)t[n-1-i]=s[i];
        t[n]='';
        L[0]=v[s[0]-'a'];
        for (int i=1;i<n;i++)L[i]=L[i-1]+v[s[i]-'a'];
        R[n-1]=v[s[n-1]-'a'];
        for (int i=n-2;i>=0;i--)R[i]=R[i+1]+v[s[i]-'a'];
        EXKMP(s,t,n,n);
        for (int i=0;i<n;i++)R[i]=(exmatch[i]==n-i)?R[i]:0;
        EXKMP(t,s,n,n);
        for (int i=0;i<n;i++)L[i]=(exmatch[n-1-i]==i+1)?L[i]:0;
        int ans=0;
        for (int i=0;i<n-1;i++)ans=max(ans,L[i]+R[i+1]);
        printf("%d
",ans);
    }
    return 0;
}