1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 int p[1000100],val[500100];

 5 char s[500100];

 6 map<char,int> mp;

 7

 8 void Manacher(char str[])

 9 {

10     memset(p,0,sizeof(p));

11     string s="$#";

12     int len=strlen(str);

13     for(int i=0;i<len;i++){

14         s+=str[i];

15         s+='#';

16     }

17     int mx=0,id=0,reslen=0,rescenter=0;

18     len=s.length();

19     for(int i=1;i<=len;i++){

20         if(mx>i) p[i]=min(p[2*id-i],mx-i);

21         else p[i]=1;

22         while(s[i+p[i]]==s[i-p[i]]) p[i]++;

23         if(mx<i+p[i]){

24             mx=i+p[i];

25             id=i;

26         }

27     }

28 }

29

30 int main()

31 {

32     int t;

33     cin>>t;

34     while(t--){

35         mp.clear();

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

37             int x;

38             cin>>x;

39             mp['a'+i]=x;

40         }

41         cin>>s;

42         int len=strlen(s);

43         for(int i=0;i<len;i++){

44             if(!i) val[i]=mp[s[i]];

45             else val[i]=val[i-1]+mp[s[i]];

46         }

47         int ans=0;

48         Manacher(s);

49         for(int i=1;i<len;i++){

50             int p1=0,p2=0;

51             int x=i*2+1;

52             x=x/2+1;      ///<i的串的中心位置

53             int y=(len-i)*2+1;

54             y=y/2+1;

55             y=(len*2+2)-y;  ///剩下部分的中心位置

56             if(p[x]==x) p1=val[i-1];

57             if(p[y]+y==len*2+2) p2=val[len-1]-val[i-1];

58             ans=max(ans,p1+p2);

59         }

60         cout<<ans<<endl;

61     }

62     return 0;

63 }

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 ///next[i]： T[i]到T[m - 1]与T(模式串)的最长相同前缀长度；

 5 ///extend[i]： S[i]到S[n - 1]（原串）与T的最长相同前缀长度。

 6

 7 const int maxn=500100;   //字符串长度最大值

 8 int nt[maxn],ex1[maxn],ex2[maxn]; //ex数组即为extend数组

 9 int val[30];

10

11 //预处理计算next数组

12 void GETNEXT(char *str)

13 {

14     int i=0,j,po,len=strlen(str);

15     nt[0]=len;    //初始化nt[0]

16     while(str[i]==str[i+1]&&i+1<len) i++;    //计算nt[1]

17     nt[1]=i;

18     po=1;       //初始化po的位置

19     for(i=2;i<len;i++){

20         if(nt[i-po]+i<nt[po]+po) nt[i]=nt[i-po];    //第一种情况，可以直接得到nt[i]的值

21         else{    //第二种情况，要继续匹配才能得到nt[i]的值

22             j=nt[po]+po-i;

23             if(j<0) j=0;    //如果i>po+nt[po],则要从头开始匹配

24             while(i+j<len&&str[j]==str[j+i]) j++;   //计算nt[i]

25             nt[i]=j;

26             po=i;   //更新po的位置

27         }

28     }

29 }

30

31 //计算extend数组

32 void EXKMP(char *s1,char *s2,int *ex)      ///s1的后缀和s2的前缀匹配

33 {

34     int i=0,j,po,len=strlen(s1),l2=strlen(s2);

35     GETNEXT(s2);    //计算子串的next数组

36     while(s1[i]==s2[i]&&i<l2&&i<len) i++;   //计算ex[0]

37     ex[0]=i;

38     po=0;   //初始化po的位置

39     for(i=1;i<len;i++){

40         if(nt[i-po]+i<ex[po]+po) ex[i]=nt[i-po];      //第一种情况，直接可以得到ex[i]的值

41         else{    //第二种情况，要继续匹配才能得到ex[i]的值

42             j=ex[po]+po-i;

43             if(j<0) j=0;     //如果i>ex[po]+po则要从头开始匹配

44             while(i+j<len&&j<l2&&s1[j+i]==s2[j]) j++;   //计算ex[i]

45             ex[i]=j;

46             po=i;   //更新po的位置

47         }

48     }

49 }

50

51 char s[maxn];

52 int sum[maxn];

53 char p[maxn];

54

55 int main()

56 {

57     int t;

58     cin>>t;

59     while(t--){

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

61             cin>>val[i];

62         cin>>s;

63         int len=strlen(s);

64         for(int i=0;i<len;i++)

65             if(!i) sum[i]=val[s[i]-'a'];

66             else sum[i]=val[s[i]-'a']+sum[i-1];

67         strcpy(p,s);

68         reverse(p,p+len);

69         EXKMP(s,p,ex1); //s做主串

70         EXKMP(p,s,ex2); //p做主串

71         int ans=0;

72         for(int i=1;i<len;i++){

73             int ans1=0,ans2=0;

74             if(ex1[i]+i==len) ans1=sum[len-1]-sum[i-1];     //s中的0~i-1;

75             if(ex2[len-i]==i) ans2=sum[i-1];        //s中的i~len-1

76             ans=max(ans,ans1+ans2);

77         }

78         cout<<ans<<endl;

79     }

80     return 0;

81 }