【Caioj1462】回文串

Source and Judge

Caioj1462

Problem

【Description】
给出26个字母所代表的权值和一个字符串,要求把字符串分成两段(每一段长度至少为1,也就是必须要有字符),假如这一段子串是一个回文串,那么加上该串所有字符权值之和,求最大的权值和。
【Input】
输入一个整数T,表示数据组数.
每组数据第一行输入26个数,表示26个字母的权值,第二行输入一个字符串
【Output】
输出每组数据的最大权值和
【Limited conditions】
保证字符串内全是小写字母,2<=字符串长度<=500000
【Sample input】
2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aba
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
acacac
【Sample output】
1
6
【Sample explanation】

Record

30min

Analysis

请先思考

对于回文字符串,常用的特性:对称性
然而有个更通俗易懂大众化的但是很容易被忽略的特性:反转后与原串一样
而exkmp正好可以后缀匹配另一个的最长前缀

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=510000;
//*******************全局定义*******************
char sa[MAXN],sb[MAXN];
int la,lb;
int ext[MAXN],ex[MAXN];
//*******************实现*******************
void pre_exkmp()
{
ext[1]=lb;
ext[2]=0;while(2+ext[2]<=lb and sb[1+ext[2]]==sb[2+ext[2]]) ext[2]++;
int k=2,rx=k+ext[k]-1;
for(int i=3;i<=lb;i++)
{
int j=i-k+1,L=ext[j];//对应点
if(L<rx-i+1) ext[i]=L;
else {ext[i]=mymax(rx-i+1,0);while(i+ext[i]<=lb and sb[1+ext[i]]==sb[i+ext[i]]) ext[i]++;}
if(i+ext[i]-1>rx) k=i,rx=k+ext[k]-1;
}
}
void exkmp()
{
pre_exkmp();
ex[1]=0;while(1+ex[1]<=lb and sb[1+ex[1]]==sa[1+ex[1]]) ex[1]++;
int k=1,rx=k+ex[k]-1;
for(int i=2;i<=la;i++)
{
int j=i-k+1,L=ext[j];//对应点
if(L<rx-i+1) ex[i]=L;
else {ex[i]=mymax(rx-i+1,0);while(1+ex[i]<=lb and i+ex[i]<=la and sb[1+ex[i]]==sa[i+ex[i]]) ex[i]++;}
if(i+ex[i]-1>rx) k=i,rx=k+ex[k]-1;
}
}
int cc[300];
int sum[MAXN];
bool f[MAXN];
int solve()
{
for(char i='a';i<='z';i++) scanf("%d",&cc[i]);
scanf("%s",sa+1);la=lb=strlen(sa+1);
memcpy(sb,sa,sizeof(sa));
std::reverse(sb+1,sb+lb+1);
exkmp();
for(int i=2;i<=lb;i++) f[i]=(ex[i]==lb-i+1);
std::swap(sa,sb);
exkmp();
for(int i=1;i<=lb;i++) sum[i]=sum[i-1]+cc[sa[i]];
int ans=0;
for(int i=1;i<=lb-1;i++)
{
int tmp=0;
if(f[lb-i+1]) tmp+=sum[i];
if(ex[i+1]==lb-i) tmp+=sum[lb]-sum[i];
ans=mymax(ans,tmp);
}
return ans;
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
int T;scanf("%d",&T);
while(T--) printf("%d\n",solve());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/回文串.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%