P3649 [APIO2014]回文串(回文树)
题目描述
给你一个由小写拉丁字母组成的字符串 ss 。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ss ,求所有回文子串中的最大存在值。
输入输出格式
输入格式:
一行,一个由小写拉丁字母(a~z)组成的非空字符串 ss 。
输出格式:
输出一个整数,表示所有回文子串中的最大存在值。
输入输出样例
输入样例#1: 复制
abacaba
输出样例#1: 复制
7
输入样例#2: 复制
www
输出样例#2: 复制
4
说明
【样例解释1】
用 \(\lvert s \rvert\) 表示字符串 ss 的长度。
一个字符串 \(s_1\) \(s_2\) \(\dots\) \(s_{\lvert s \rvert}\) 的子串是一个非空字符串 \(s_i\) \(s_{i+1}\) \(\dots s_j\) ,其中 \(1\) \(\leq\) i \(\leq\) j \(\leq\) \(\lvert s \rvert\) 。每个字符串都是自己的子串。
一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。
这个样例中,有 7 个回文子串 a,b,c,aba,aca,bacab,abacaba。他们的存在值分别为 4, 2, 1, 6, 3, 5, 7 。
所以回文子串中最大的存在值为 77 。
第一个子任务共 8 分,满足1≤∣s∣≤100 。
第二个子任务共 15 分,满足1≤∣s∣≤1000 。
第三个子任务共 24 分,满足 1≤∣s∣≤10000 。
第四个子任务共 26 分,满足 1≤∣s∣≤100000 。
第五个子任务共 27 分,满足 1≤∣s∣≤300000 。
题解
这题没有什么好说的。
明显是回文树(也称回文自动机)的模板题。
我们只需要利用一下回文树的cnt数组,它表示的是当前回文串出现的次数,然后再与len数组相乘就OK了。len表示当前回文串的长度。
菜鸡代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
int fail,ch[26],len,cnt;
}t[300100];
char s[300010];
int tot;
ll ans=0;
void solve()
{
int len=strlen(s+1),k=0;s[0]='#';
t[0].fail=t[1].fail=1;t[1].len=-1;tot=1;
for(int i=1;i<=len;i++){
while(s[i-t[k].len-1]!=s[i])k=t[k].fail;
if(!t[k].ch[s[i]-'a']){
t[++tot].len=t[k].len+2;
int j=t[k].fail;
while(s[i-t[j].len-1]!=s[i])j=t[j].fail;
t[tot].fail=t[j].ch[s[i]-'a'];
t[k].ch[s[i]-'a']=tot;
}
k=t[k].ch[s[i]-'a'];
t[k].cnt++;
}
for(int i=tot;i>=2;i--){
t[t[i].fail].cnt+=t[i].cnt;
if((long long)t[i].cnt*t[i].len>ans)
ans=(long long)t[i].cnt*t[i].len;
}
}
int main()
{
cin>>s+1;
int len=strlen(s+1);
solve();
cout<<ans<<endl;
return 0;
}
最新文章
- CNN 入门学习资料整理
- loading插件(原创)
- SSH使用密钥登录并禁止口令登录实践
- string用法
- 在Struts2中配置Action
- 自动化:Appium运行成功,取得一个小的胜利
- 第三方框架FMDB
- C 中随机数
- ANDROID_MARS学习笔记_S01原始版_023_MP3PLAYER005_用广播BroacastReciever实现后台播放不更新歌词
- [DEncrypt] Encrypt--加密/解密/MD5加密 (转载)
- 小K的H5之旅-实战篇(一)
- Dynamics CRM2016 New features in Microsoft Dynamics CRM Online 2015 Update 1 are now available
- XUnit 依赖注入
- API认证&;SDK&;RESTful
- Linux下Redis安装使用教程
- oracle-安装-init.sh
- LeetCode - 198 简单动态规划 打家劫舍
- nginx高性能webserver具体解释(1)--安装nginx
- 【Android开发经验】Cannot generate texture from bitmap异常的解决方式
- style=";display:none";隐藏html的标签