hdu3613

题解：

EX_KMP

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

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

暴力枚举拆开了的位置

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

int v[],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[]=m;

    for (int i=,po=;t[i];i++)

     {

        int P=po+exnxt[po];

        exnxt[i]=max(min(exnxt[i-po],P-i),);

        while (i+exnxt[i]<m&&t[exnxt[i]]==t[i+exnxt[i]])exnxt[i]++;

        if (i+exnxt[i]>P) po=i;

     }

    for (int i=,po=;s[i];i++)

     {

        int P=po+exmatch[po];

        exmatch[i]=max(min(exnxt[i-po],P-i),);

        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,,sizeof exmatch);

        for (int i=;i<;i++) scanf("%d",&v[i]);

        scanf("%s",&s);

        n=strlen(s);

        if (n<)

         {

            puts("");

            continue;

         }

        for (int i=;i<n;i++)t[n--i]=s[i];

        t[n]='\0';

        L[]=v[s[]-'a'];

        for (int i=;i<n;i++)L[i]=L[i-]+v[s[i]-'a'];

        R[n-]=v[s[n-]-'a'];

        for (int i=n-;i>=;i--)R[i]=R[i+]+v[s[i]-'a'];

        EXKMP(s,t,n,n);

        for (int i=;i<n;i++)R[i]=(exmatch[i]==n-i)?R[i]:;

        EXKMP(t,s,n,n);

        for (int i=;i<n;i++)L[i]=(exmatch[n--i]==i+)?L[i]:;

        int ans=;

        for (int i=;i<n-;i++)ans=max(ans,L[i]+R[i+]);

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

    }

    return ;

}