【bzoj3676】[Apio2014]回文串 回文自动机
2024-08-24 21:27:02
题目描述
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。
输入
输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。
输出
输出一个整数,为逝查回文子串的最大出现值。
样例输入
【样例输入l】
abacaba
【样例输入2]
www
样例输出
【样例输出l】
7
【样例输出2]
4
题解
回文自动机裸题
关于PAM个人暂时理解不是很深入,挖坑待填。
本题只需要统计fail树的子树大小,再乘上回文串长度即可。
#include <cstdio>
#include <algorithm>
#define N 300010
using namespace std;
typedef long long ll;
int next[N][26] , fa[N] = {1 , 1} , len[N] = {0 , -1} , si[N] , tot = 1 , last;
char str[N];
void insert(int c , int now)
{
int p = last;
while(str[now - len[p] - 1] != str[now]) p = fa[p];
if(!next[p][c])
{
int q = fa[p];
while(str[now - len[q] - 1] != str[now]) q = fa[q];
fa[++tot] = next[q][c] , next[p][c] = tot , len[tot] = len[p] + 2;
}
last = next[p][c] , si[last] ++ ;
}
int main()
{
int i;
ll ans = 0;
scanf("%s" , str + 1);
for(i = 1 ; str[i] ; i ++ ) insert(str[i] - 'a' , i);
for(i = tot ; i > 1 ; i -- ) ans = max(ans , (ll)si[i] * len[i]) , si[fa[i]] += si[i];
printf("%lld\n" , ans);
return 0;
}
最新文章
- Timequest GUI
- mysqli操作数据库
- ANSI Common Lisp Practice - My Answers - Chatper - 2
- C++ 中 int 转string, 以及10进制转2进制
- 【原创】.NET读写Excel工具Spire.Xls使用(5)重量级的Excel图表功能
- 第七周PSP
- dig与dns基本理论——解析和缓存
- MySql表大小、行大小和列大小的限制
- MFC中错误知识总结(一)
- Cocos2d-x场景切换相关函数介绍
- kaggle之手写体识别
- Js中call apply函数以及this用法
- BZOJ 4004: [JLOI2015]装备购买 [高斯消元同余 线性基]
- Sharepoint模态窗体(实战)
- sort 用法
- Breakout 打砖块
- Nginx ssl证书部署方法
- Delphi 7调用C语言编写的DLL
- 20170716xlVba销售明细转销售单据
- Django REST framework 之 API认证