題目大意：
給個字符串S，要把S分成兩段T1,T2，每個字母都有一個對應的價值，如果T1，T2是回文串（從左往右或者從右往左讀，都一樣），那么他們就會有一個價值，這個價值是這個串的所有字母價值之和，如果不是回文串，那么這串價值就為0。問最多能獲得多少價值？ ? 對于我們只需要枚舉掃描一遍extend數組，掃描到的當前位置之前為前半部分T1， 然后用根據extend數組可以判斷T1是否是回文。那后半部分T2呢？? 剛才是用S去匹配T， 如果要求后綴，只需要用T去匹配S，再得到一個數組extend2即可，根據這個extend2判斷后半部分T2是否是回文。

?

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 #define cl(a) memset(a,0,sizeof(a)) 13 #define ts printf("*****\n"); 14 const int MAXN=500005; 15 int n,m,tt; 16 char s1[MAXN],s2[MAXN]; 17 int v[29],sum[MAXN]; 18 void pre_EKMP(char x[],int m,int nextt[]) 19 { 20 nextt[0]=m; 21 int j=0; 22 while(j+1<m && x[j]==x[j+1])j++; 23 nextt[1]=j; 24 int k=1; 25 for(int i=2;i<m;i++) 26 { 27 int p=nextt[k]+k-1; 28 int L=nextt[i-k]; 29 if(i+L<p+1)nextt[i]=L; 30 else 31 { 32 j=max(0,p-i+1); 33 while(i+j<m && x[i+j]==x[j])j++; 34 nextt[i]=j; 35 k=i; 36 } 37 } 38 } 39 void EKMP(char x[],int m,char y[],int n,int nextt[],int extend[]) 40 { 41 pre_EKMP(x,m,nextt); 42 int j=0; 43 while(j<n && j<m && x[j]==y[j])j++; 44 extend[0]=j; 45 int k=0; 46 for(int i=1;i<n;i++) 47 { 48 int p=extend[k]+k-1; 49 int L=nextt[i-k]; 50 if(i+L<p+1)extend[i]=L; 51 else 52 { 53 j=max(0,p-i+1); 54 while(i+j<n && j<m && y[i+j]==x[j])j++; 55 extend[i]=j; 56 k=i; 57 } 58 } 59 } 60 int nextt[MAXN],extend1[MAXN],extend2[MAXN]; 61 int main() 62 { 63 int i,j,k; 64 #ifndef ONLINE_JUDGE 65 freopen("1.in","r",stdin); 66 #endif 67 scanf("%d",&tt); 68 while(tt--) 69 { 70 for(i=0;i<26;i++) 71 { 72 scanf("%d",&v[i]); 73 } 74 scanf("%s",s1); 75 int len=strlen(s1); 76 for(i=0;i<len;i++) 77 { 78 sum[i+1]=v[s1[i]-'a']+sum[i]; 79 } 80 strcpy(s2,s1); 81 strrev(s2); 82 EKMP(s2,len,s1,len,nextt,extend1); 83 EKMP(s1,len,s2,len,nextt,extend2); 84 int maxx=0; 85 for(i=1;i<len;i++) //枚舉斷點 86 { 87 int tot=0; 88 if(i+extend1[i]==len) //這里求的是斷點后面的 89 { 90 tot+=sum[len]-sum[i]; 91 } 92 int ll=len-i; 93 if(ll+extend2[ll]==len) 94 { 95 tot+=sum[len]-sum[ll]; 96 } 97 maxx=max(maxx,tot); 98 } 99 printf("%d\n",maxx); 100 } 101 }

?

轉載于:https://www.cnblogs.com/cnblogs321114287/p/4466487.html

總結

以上是生活随笔為你收集整理的hdu 3613 扩展kmp+回文串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。