HDU - 3613 Best Reward（manacher或拓展kmp）
传送门：HDU - 3613
题意：给出26个字母的价值，然后给你一个字符串，把它分成两个字符串，字符串是回文串才算价值，求价值最大是多少。
题解：这个题可以用马拉车，也可以用拓展kmp。
①Manacher：先记录下第i个字符的价值，然后求前缀和。然后遍历分的位置，分别判断前半段和后半段是否为回文串，是回文串的加上这段的价值（前缀和相减），更新最大价值。
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 }
②拓展kmp：用原串和反串进行比较，第一次原串做主串，第二次反串做主串。遍历分的位置，如果ex1[i]+i==len，那么说明s中的0~i-1为回文串，如果ex2[len-i]==i，说明s中的i~len-1为回文串，是回文串的价值加上，记录最大的价值。
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 }
