分析:
首先原始串为S,将S逆转得到串T.(S=abcaaa,那么T=aaacba).
S串的后缀回文:即S串中区间[i,n-1]的串是不是回文?
将S作为主串,T串用扩展KMP算法去匹配S,extend1[n]数组保存匹配结果.如果extend1[i]+i==n时(n为S的长),那么以S[i]为首字符一直到底n-1位置的串是回文串,否则不是.(自己举个例子验证一下)
S串的前缀回文:即S串中区间[0,i-1]的串是不是回文?
将T作为主串,S串用扩展KMP算法去匹配T,extend2[n]数组保存匹配结果.如果extend2[len-i]+len-i==n时(n为S的长),那么以S[i-1]为尾字符一直到0位置的串是回文串,否则不是.(自己举个例子验证一下)
仔细思考下上面的模型.
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> using namespace std; void EKMP(char s[],char t[],int nex[],int extend[])//s为主串，t为模板串 { int i,j,p,L; int lens=strlen(s); int lent=strlen(t); nex[0]=lent; j=0; while(j+1<lent && t[j]==t[j+1])j++; nex[1]=j; int a=1; for(i=2;i<lent;i++) { p=nex[a]+a-1; L=nex[i-a]; if(i+L<p+1)nex[i]=L; else { j=max(0,p-i+1); while(i+j<lent && t[i+j]==t[j])j++; nex[i]=j; a=i; } } j=0; while(j<lens && j<lent && s[j]==t[j])j++; extend[0]=j; a=0; for(i=1;i<lens;i++) { p=extend[a]+a-1; L=nex[i-a]; if(L+i<p+1)extend[i]=L; else { j=max(0,p-i+1); while(i+j<lens && j<lent && s[i+j]==t[j])j++; extend[i]=j; a=i; } } } const int MAXN=500010; char str1[MAXN],str2[MAXN]; int sum[MAXN]; int v[27]; int nex[MAXN]; int extend1[MAXN],extend2[MAXN]; int main() { int T; scanf("%d",&T); while(T--) { for(int i=0;i<26;i++) scanf("%d",&v[i]); scanf("%s",str1); int len=strlen(str1); sum[0]=0; for(int i=0;i<len;i++) { sum[i+1]=sum[i]+v[str1[i]-‘a‘]; str2[i]=str1[len-1-i]; } str2[len]=0; EKMP(str2,str1,nex,extend1); EKMP(str1,str2,nex,extend2); int ans=-10000; //需要保证分成两部分，所以i从1到len-1 for(int i=1;i<len;i++) { int tmp=0; if(i+extend1[i]==len) { tmp+=sum[len-i]; } int pos=len-i; if(pos+extend2[pos]==len) { tmp+=sum[len]-sum[pos]; } if(tmp>ans)ans=tmp; } printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/bxd123/p/10679075.html
