hdu 3613

题目

这题比较考对manacher的理解，首先我们考虑如何判断前$i$位和后$j$位是回文串（好多博客对这个点都没说清楚）。首先p[i]指的是以i为中心的最长回文半径（在manacher算法的新串中），且p[i]-1是在原串的回文长度，那我们是不是可以想，如果在新串中，以i为中心的串半径能达到左边界或者右边界，就说明前$i$位或者后$j$位是回文串。既然这样，碰到左边界了，p[i]-1就是前$i$位可以组成回文串，后$j$位同理，可能语言逻辑不大清晰，那就看看代码吧。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#include<set>
#define IO ios::sync_with_stdio(false)
//#define int long long
using namespace std;
const int N=500010;
char s[N],ns[N*2];
int len,v[30],sum[N],t,pre[N],suf[N],p[N*2];
void manacher()
{
    //memset(ns,0,sizeof(ns));
    ns[0]='$';
    ns[1]='#';
    int j=2;
    for(int i=1;i<=len;i++)
    {
        ns[j++]=s[i];
        ns[j++]='#';
    }
    ns[j]='\0';
    int nlen=j;
    int maxlen=-1,id,mx=0;
    for(int i=1;i<=nlen;i++)
    {
        if(i<mx)
        {
            p[i]=min(p[2*id-i],mx-i);
        }
        else
        {
            p[i]=1;
        }
        while(ns[i-p[i]]==ns[i+p[i]])p[i]++;
        if(mx<i+p[i])
        {
            id=i;
            mx=i+p[i];
        }
        if(i==p[i])pre[p[i]-1]=1;//碰到左边界
        if(i+p[i]==nlen)suf[p[i]-1]=1;//碰到右边界
    }
}
int main()
{
    //IO;
    cin>>t;
    while(t--)
    {
        memset(pre,0,sizeof(pre));
        memset(suf,0,sizeof(suf));
        for(int i=1;i<=26;i++)
        {
            scanf("%d",&v[i]);
        }
        scanf("%s",s+1);
        len=strlen(s+1);
        manacher();
        for(int i=1;i<=len;i++)
        {
            sum[i]=sum[i-1]+v[s[i]-'a'+1];
        }
        int ans=-(1<<29);
        for(int i=1;i<=len-1;i++)
        {
            int cnt=0;
            cnt+=pre[i]*sum[i];
            cnt+=suf[len-i]*(sum[len]-sum[i]);
            ans=max(ans,cnt);
        }
        printf("%d\n",ans);
    }
}

本文地址：https://blog.csdn.net/qq_37073764/article/details/107880111