不得不说这是一道好题（前排膜拜灯教授），其实这道题如果不说是EXKMP，很容易就想到Manacher（好像也可以这样做）
回到这道题，这样只有一个字符串，还要求回文？立刻想到了将这个串和它的反串跑EXKMP，举个例子：
假设字符串s[0]是acacac，那它的反串s[1]就是cacaca，互相跑EXKMP就有：
ex[0]={0,0,5,0,3,0,1}//这里的定义是以s[0]为模版串
ex[1]={0,0,5,0,3,0,1}
然后就可以枚举断的地方，假设a|cacac i=2
那定义一个j等于len-(i-1)+1就指向cacaca的最后一个a，等于6，然后得到ex[1][6]有多少个匹配的，当然了，6+ex[1][6]-1要等于len才行，不然这两个串就不是完全匹配的了。同理i后面的cacac也是这样搞，（当然你可以像灯教授和肉丝鸡掌一样搞个前缀和什么的省时间 %%%%%）
然而昨天灯教授故意卡了我，搞得我现在又要改成用前缀和了。。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int a[30]; char s[2][510000]; int p[2][510000],ex[2][510000]; void exkmp(int len,int w) { int x,k; p[1-w][1]=len; x=1;while(s[1-w][x]==s[1-w][x+1]&&x<=len)x++; p[1-w][2]=x-1;k=2; for(int i=3;i<=len;i++) { int P=k+p[1-w][k]-1,L=p[1-w][i-k+1]; if(i-k+L<P-k+1)p[1-w][i]=L; else { int j=max(P-i+1,0); while(s[1-w][1+j]==s[1-w][i+j]&&i+j<=len)j++; p[1-w][i]=j;k=i; } } x=1;while(s[w][x]==s[1-w][x]&&x<=len)x++; ex[w][1]=x-1;k=1; for(int i=2;i<=len;i++) { int P=k+ex[w][k]-1,L=p[1-w][i-k+1]; if(i-k+L<P-k+1)ex[w][i]=L; else { int j=max(P-i+1,0); while(s[1-w][1+j]==s[w][i+j]&&i+j<=len)j++; ex[w][i]=j;k=i; } } } int qz[2][510000]; void getsum(int len) { int ans=0,ss,x,tp; for(int i=2;i<=len;i++) { ss=0;int j=len-(i-1)+1; if(j+ex[1][j]-1==len)ss+=qz[0][ex[1][j]]; if(i+ex[0][i]-1==len)ss+=qz[1][ex[0][i]]; if(ss>ans)ans=ss; } printf("%d ",ans); } int main() { int T; scanf("%d",&T); while(T--) { for(int i=1;i<=26;i++)scanf("%d",&a[i]); scanf("%s",s[0]+1);int len=strlen(s[0]+1); for(int i=1;i<=len;i++)s[1][i]=s[0][len-i+1]; qz[0][0]=0;qz[0][1]=0; for(int i=1;i<=len;i++) { qz[0][i]=qz[0][i-1]+a[s[0][i]-'a'+1]; qz[1][i]=qz[1][i-1]+a[s[1][i]-'a'+1]; } exkmp(len,0);exkmp(len,1); getsum(len); } return 0; }