| 题目名称 | 1985. [APIO 2014] Palindromes |
|---|---|
| 输入输出 | apio2014_palindrome.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 76 |
| 题目来源 |
 Chenyao2333
于2015-05-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：96， 提交：186， 通过率：51.61% | ||||
 Marvolo |
100 | 0.058 s | 5.98 MiB | C++ |
 AntiLeaf |
100 | 0.194 s | 33.79 MiB | C++ |
 ztx |
100 | 0.223 s | 34.17 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.230 s | 38.19 MiB | C++ |
|
AntiLeaf |
100 | 0.240 s | 33.76 MiB | C++ |
 gls1196 |
100 | 0.261 s | 33.79 MiB | C++ |
 Cooook |
100 | 0.293 s | 33.79 MiB | C++ |
 kito |
100 | 0.303 s | 33.76 MiB | C++ |
|
kito |
100 | 0.313 s | 34.91 MiB | C++ |
|
Go灬Fire |
100 | 0.313 s | 39.92 MiB | C++ |
| 关于 Palindromes 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
玄学T……max函数写在count里才A。
| ||||
|
回文自动机大发吼啊！
| ||||
|
sam
| ||||
|
manacher + SA + 二分，O(nlogn)轻松水过
| ||||
|
战斗民族的回文自动机真是劲啊！
| ||||
|
自从有了又短又快♂的回文树，再也不写马拉车+后缀自动机辣
| ||||
|
淦马拉车+后缀自动机 --> 76个测试点最后连T带E。。。已报警。
| ||||
|
啊哈哈……用两种方法AC了
| ||||
|
COGS第一份后缀自动机.
| ||||
|
scanf("%s") + memset 费时2s
ztx
2015-05-27 20:41
2楼
| ||||
Shirry
Rapiz
__stdcall
FoolMike
sxysxy
TenderRun
stdafx.h1985. [APIO 2014] Palindromes
★★★ 输入文件：apio2014_palindrome.in
输出文件：apio2014_palindrome.out
简单对比时间限制：5 s 内存限制：256 MiB
【题目描述】
给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 s，求所有回文子串中的最大存在值。
【输入格式】
一行，一个由小写拉丁字母（a~z）组成的非空字符串 s。
【输出格式】
输出一个整数，表示所有回文子串中的最大存在值。
【样例输入】
abacaba
【样例输出】
7
【提示】
一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有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。
【来源】
APIO2014