KMP_Best Reward

大意：把一个字符串分成两串，假如一个字符串是回文串就可以加上它的VALUE,否则它的VALUE为0；

        KMP的特点是可以求出前缀与后面的字符串是否匹配，

        注意回文串的特点，所以当我们把回文串反转的时候会发现与前面的字符串匹配，

        然后将字符串整个反转可以求出后缀的，

       利用其特点可以快速判断回文串，

   CODE;

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string.h>
#define N  500008
using namespace std;
typedef long long ll;

char s[2*N];
int next[2*N];
int a[150];
int sum[N*2],pos[2*N],pre[2*N];


void get_next(char *s)//NEXT数组
{
   next[0]=-1;
   int k=-1,i=0;
   int l=strlen(s);
   while (i<l)
   {
       if (k==-1||s[i]==s[k])
       {
           k++;i++;
           next[i]=k;
       }
       else k=next[k];
   }
}

int main()
{
    int cas;
    scanf("%d",&cas);
    
    while (cas--)
    {
          memset(pos,0,sizeof(pos));
          memset(pre,0,sizeof(pre));
      for (int i=0;i<26;i++) scanf("%d",&a[i]);
      scanf("%s",s);
      
      int len=strlen(s);
      for (int i=1;i<=len;i++)  sum[i]=sum[i-1]+a[s[i-1]-'a'];//预先处理SUM数组，注意我们把A[I]的值移位了。
         s[len]='#';
         int k=len,l=len;
         while (k) s[++l]=s[--k];//字符串反接在后面
      s[++l]='';
      get_next(s);
      int dol=l;
      while (next[dol]) {pre[next[dol]]=len+1;dol=next[dol];}
      for (int i=0;i<len;i++)
        swap(s[i],s[len+1+i]);

        get_next(s);
        dol=l;
     while (next[dol]) {pos[next[dol]]=len+1;dol=next[dol];};

     int ans=-123;
     for (int i=1;i<len;i++)//核心代码,计算值
     {
         int ss=0;
         if (pre[i]==len+1) ss+=sum[i];
         if (pos[len-i]==len+1) ss+=sum[len]-sum[i];
         ans=max(ans,ss);
     }
        printf("%d
",ans);

    }
    return 0;
}