hdu3613 Best Reward 扩展kmp or O(n)求最大回文子串

/**
题目：hdu3613 Best Reward
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3613
题意:有一个字符串，把他切成两部分。
如果这部分是回文串，那么他的值为所有字母的权值和。否则这部分值为0；这两部分的值和为该切法的权值。
求最大的切法的权值。
思路：
如果能够判断[0,i],[i,n-1]是一个回文串(0<=i<n）那么就可以枚举i，计算切割位置为i时候两部分的贡献和。
取最大的。
利用O(n)的算法求最长回文子串的做法获得f[i]；表示以第i个字符为中心的最长回文子串的长度；
就可以获得l[i],r[i];
l[i]=1表示[0,i]是一个回文串.r[i]=1表示[i,n-1]是一个回文串。*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<set>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+;///给定的长度
char s[maxn*], t[maxn];///要乘以2，因为构造了'*'
int f[maxn*];///令f[i] 表示以第i个字符为中心的最长回文子串的长度
int sum[maxn*], w[];
int l[maxn*], r[maxn*];///l[i]=1表示[0,i]是一个回文串.r[i]=1表示[i,n-1]是一个回文串。
int longest(char *a)///最长回文子串
{
int z = ;
for(int i = ; a[i]!='\0'; i++){
s[z++] = a[i];
s[z++] = '*';
}
z--;
s[z] = '\0';
int j = ;
int ans = ;
f[] = ;
for(int i = ; i < z; i++){
if(f[j]-*(i-j)<=) {
f[i] = ;
}else{
f[i] = min(f[*j-i],f[j]-*(i-j));
}
int l = i-f[i]/-, r = i+f[i]/+;
while(l>=&&r<z&&s[l]==s[r]){
l--, r++;
f[i]+=;
}
if(f[i]/+i>f[j]/+j){
j = i;
}
if(f[i]>ans){
ans = f[i];
}
}
int mas = ;
for(int i = ; i < z; i++){
if(f[i]==ans){
int l = i-f[i]/, r = i+f[i]/;
int cnt;
if(s[l]=='*'){
cnt = f[i]/;
}else cnt = f[i]/+;
mas = max(mas,cnt);
}
}
return mas;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
int cas = ;
cin>>T;
while(T--){
for(int i = ; i < ; i++) scanf("%d",&w[i]);
scanf("%s",t);
longest(t);
int n = strlen(s);
sum[] = w[s[]-'a'];
for(int i = ; i < n; i++){
if(s[i]=='*') sum[i] = sum[i-]+;
else sum[i] = sum[i-]+w[s[i]-'a'];
}
memset(l, , sizeof l);
memset(r, , sizeof r);
for(int i = ; i < n; i++){
int L = i-(f[i]-)/;
int R = i+(f[i]-)/;
if(L==){
l[R] = ;
}
if(R==n-){
r[L] = ;
}
}
int ans = -INF, ansa, ansb;
for(int i = ; i < n-; i++){
if(i%){
if(l[i-]){
ansa = sum[i-];
}else ansa = ;
if(r[i+]){
ansb = sum[n-]-sum[i-];
}else ansb = ;
}else
{
if(l[i-]){
ansa = sum[i-];
}else ansa = ;
if(r[i]){
ansb = sum[n-]-sum[i-];
}else ansb = ;
} ans = max(ans,ansa+ansb);
}
printf("%d\n",ans);
}
return ;
}

/**
题目：hdu3613 Best Reward
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3613
题意:有一个字符串，把他切成两部分。
如果这部分是回文串，那么他的值为所有字母的权值和。否则这部分值为0；这两部分的值和为该切法的权值。
求最大的切法的权值。
思路：
如果能够判断[0,i],[i,n-1]是一个回文串(0<=i<n）那么就可以枚举i，计算切割位置为i时候两部分的贡献和。
取最大的。扩展kmp的做法。
先计算l[i]=1，表示[0,i]是一个回文串；那么[0,k1]与[k2,i]相等。0是固定的。
获得原串t的反转串s。求extend[i]，表示s串从[i,n-1]与原串t的最长公共前缀。
枚举s串的i。那么从[i,n-1]的长度n-i；如果extend[i]*2+1>=n-i那么表示原串t中的[0,n-1-i]是一个回文串即l[n-1-i] = 1;现在求r[i]=1,表示[i,n-1]是一个回文串；那么[i,k1]与[k2,n-1]相等。n-1是固定的。
求extend[i],表示t串从[i,n-1]与s串的最长公共前缀。
枚举t串的i。那么从[i,n-1]的长度为n-i;如果extend[i]*2+1>=n-i那么表示原串[i,n-1]是一个回文串即r[i] = 1;*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5+;
char s[maxn], t[maxn];
int f[maxn], Next[maxn], extend[maxn];
int sum[maxn], w[];
int l[maxn], r[maxn];///l[i]=1表示[0,i]是一个回文串.r[i]=1表示[i,n-1]是一个回文串。
void GetNext(char *T,int* next)
{
int a=;
int Tlen=strlen(T);
next[]=Tlen;
while(a<Tlen-&&T[a]==T[a+]) a++;
next[]=a;
a=;
for(int k=;k<Tlen;k++)
{
int p=a+next[a]-,L=next[k-a];
if((k-)+L>=p)
{
int j=(p-k+)>? p-k+:;
while(k+j<Tlen&&T[k+j]==T[j]) j++;
next[k]=j;
a=k;
}
else next[k]=L;
}
}void GetExtend(char *S,char *T,int* next,int* extend)
{
int a=;
GetNext(T,next);
int Slen=strlen(S);
int Tlen=strlen(T);
int MinLen=Slen<Tlen? Slen:Tlen;
while(a<MinLen&&S[a]==T[a]) a++;
extend[]=a;
a=;
for(int k=;k<Slen;k++)
{
int p=a+extend[a]-,L=next[k-a];
if((k-)+L>=p)
{
int j=(p-k+)>? p-k+:;
while(k+j<Slen&&j<Tlen&&S[k+j]==T[j]) j++;
extend[k]=j;
a=k;
}
else extend[k]=L;
}
}
void getlr(int* extend,int *l,int flag,int n)
{
int len;
for(int i = ; i < n; i++){
len = n-i;
if(extend[i]*+>=len){
if(flag) l[i] = ;
else l[n--i] = ;
}
}
}
void test(int *f,int n)
{
for(int i = ; i < n; i++){
printf("f[%d] = %d\n",i,f[i]);
}
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
cin>>T;
while(T--){
for(int i = ; i < ; i++) scanf("%d",&w[i]);
scanf("%s",t);
int n = strlen(t);
for(int i = ; i < n; i++) s[n--i] = t[i];
s[n] = '\0';
sum[] = w[t[]-'a'];
for(int i = ; i < n; i++){
sum[i] = sum[i-]+w[t[i]-'a'];
}
memset(l, , sizeof l);
memset(r, , sizeof r); GetExtend(s,t,Next,extend);
getlr(extend,l,,n); GetExtend(t,s,Next,extend);
getlr(extend,r,,n); int ans = -INF, ansa, ansb;
for(int i = ; i < n; i++){
if(l[i-]){
ansa = sum[i-];
}else ansa = ;
if(r[i]){
ansb = sum[n-]-sum[i-];
}else ansb = ;
ans = max(ans,ansa+ansb);
}
printf("%d\n",ans);
}
return ;
}