bzoj 3676: [Apio2014]回文串
Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最 大出现值。
Input
输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。
Output
输出一个整数,为逝查回文子串的最大出现值。
Sample Input
【样例输入l】 abacaba 【样例输入2] www
Sample Output
【样例输出l】 7 【样例输出2] 4
HINT
一个串是回文的,当且仅当它从左到右读和从右到左读完全一样。 在第一个样例中,回文子串有7个:a,b,c,aba,aca,bacab,abacaba,其中: ● a出现4次,其出现值为4:1:1=4 ● b出现2次,其出现值为2:1:1=2 ● c出现1次,其出现值为l:1:l=l ● aba出现2次,其出现值为2:1:3=6 ● aca出现1次,其出现值为1=1:3=3 ●bacab出现1次,其出现值为1:1:5=5 ● abacaba出现1次,其出现值为1:1:7=7 故最大回文子串出现值为7。 【数据规模与评分】 数据满足1≤字符串长度≤300000。
分析
回文自动机裸题 好像可以用manacher+后缀自动机做 回文自动机的算法学习:Palindromic Tree——回文树【处理一类回文串问题的强力工具】 没办法写得更好了。
代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std
;
const int N
= 310000;
long long ans
;
int len
[N
], f
[N
], a
[N
], val
[N
], ch
[N
][26], last
, sz
, n
;
void PDT_pre() {
f
[last
= sz
= 0] = 1;
len
[++sz
] = a
[n
= 0] = -1;
}
void Extend(int c
) {
a
[++n
] = c
; int p
, np
, x
;
for(p
= last
; a
[n
- len
[p
] - 1] != a
[n
]; p
= f
[p
]) ;
if(!ch
[p
][c
]) {
len
[np
= ++sz
] = len
[p
] + 2;
for(x
= f
[p
]; a
[n
- len
[x
] - 1] != a
[n
]; x
= f
[x
]) ;
f
[np
] = ch
[x
][c
]; ch
[p
][c
] = np
;
}
++val
[last
= ch
[p
][c
]];
}
void work() {
char ch
= getchar();
while(ch
< 'a' || ch
> 'z') ch
= getchar();
for(;ch
>= 'a' && ch
<= 'z'; ch
= getchar()) Extend(ch
- 'a');
}
int main() {
PDT_pre();
work();
for(int i
= sz
; i
>= 2; --i
) {
val
[f
[i
]] += val
[i
];
ans
= max(ans
, 1LL * val
[i
] * len
[i
]);
}
printf("%lld\n", ans
);
return 0;
}