题目描述

考虑一个只包含小写拉丁字母的字符串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;
}

最新文章

  1. Timequest GUI
  2. mysqli操作数据库
  3. ANSI Common Lisp Practice - My Answers - Chatper - 2
  4. C++ 中 int 转string, 以及10进制转2进制
  5. 【原创】.NET读写Excel工具Spire.Xls使用(5)重量级的Excel图表功能
  6. 第七周PSP
  7. dig与dns基本理论——解析和缓存
  8. MySql表大小、行大小和列大小的限制
  9. MFC中错误知识总结(一)
  10. Cocos2d-x场景切换相关函数介绍
  11. kaggle之手写体识别
  12. Js中call apply函数以及this用法
  13. BZOJ 4004: [JLOI2015]装备购买 [高斯消元同余 线性基]
  14. Sharepoint模态窗体(实战)
  15. sort 用法
  16. Breakout 打砖块
  17. Nginx ssl证书部署方法
  18. Delphi 7调用C语言编写的DLL
  19. 20170716xlVba销售明细转销售单据
  20. Django REST framework 之 API认证

热门文章

  1. UVA 1451 Average平均值 (数形结合,斜率优化)
  2. Android(java)学习笔记125:保存数据到SD卡 (附加:保存数据到内存)
  3. 换个语言学一下 Golang (3)——数据类型
  4. cocos2dx 加密spine文件遇到的问题(暂时没有解决方法)
  5. (73)zabbix用户认证方式 内建、HTTP Basic、LDAP
  6. 02Qt信号与槽(1)
  7. PHP将unicode转utf8最简法
  8. Applied Nonparametric Statistics-lec5
  9. x mod a=r(N对a,r)
  10. jmeter jdbc各字段的含义