HDU3613
这道题需要求给定字符串的以所有字符为中心的最长的回文字符串的长度。马拉车算法可以在线性时间内做到。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int len;
char numbers[MAXN],check[MAXN*2];
int qianzhui[MAXN];
int Len[2*MAXN];
int score[30];
void manacher()
{check[0]='@';for(int i=1;i<=2*len;i+=2){check[i]='#';check[i+1]=numbers[i/2];}check[2*len+1]='#';check[2*len+2]='$';int mx=0,po=0;for(int i=1;i<=2*len;i++){if(mx>i)Len[i]=min(mx-i,Len[2*po-i]);else Len[i]=1;while(check[i-Len[i]]==check[i+Len[i]])Len[i]++;if(Len[i]+i>mx){mx=Len[i]+i;po=i;}}
}
int main()
{int t;cin>>t;while(t--){for(int i=1;i<=26;i++)cin>>score[i];scanf("%s",numbers);len=strlen(numbers);for(int i=1;i<=len;i++)qianzhui[i]=qianzhui[i-1]+score[numbers[i-1]-'a'+1];int ans=0;manacher();for(int i=0;i<len-1;i++){int sum=0;if(Len[i+2]==i+2)sum+=qianzhui[i+1];if(Len[i+len+2]==len-i)sum+=qianzhui[len]-qianzhui[i+1];ans=max(ans,sum);}cout<<ans<<endl;}
}