后缀自动机+manacher

听说本质不同的回文串只有O(n)个

那么用manacher求出所有回文串,然后在sam上查找出现了几次就行了

sam的性质又忘了。。。

manacher也忘了。。。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + ;
int n, len, pos, mx;
long long ans;
int c[N << ], a[N << ], p[N << ], fa[N << ][], f[N << ], Pos[N];
char s[N], S[N << ];
namespace SAM
{
struct node {
int val, par;
int ch[];
} t[N << ];
int sz = , root = , last = ;
int nw(int _)
{
t[++sz].val = _;
return sz;
}
void extend(int c)
{
int p = last, np = nw(t[p].val + );
while(p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].par;
if(!p) t[np].par = root;
else
{
int q = t[p].ch[c];
if(t[q].val == t[p].val + ) t[np].par = q;
else
{
int nq = nw(t[p].val + );
memcpy(t[nq].ch, t[q].ch, sizeof(t[q].ch));
t[nq].par = t[q].par;
t[q].par = t[np].par = nq;
while(p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].par;
}
}
last = np;
Pos[t[np].val] = np;
f[np] = ;
}
int query(int l, int r)
{
int len = r - l + , now = Pos[r];
for(int i = ; i >= ; --i) if(t[fa[now][i]].val >= len) now = fa[now][i];
return f[now];
}
} using namespace SAM;
int main()
{
scanf("%s", s + );
n = strlen(s + );
for(int i = ; i <= n; ++i) extend(s[i] - 'a');
for(int i = ; i <= sz; ++i) ++c[t[i].val];
for(int i = ; i <= sz; ++i) c[i] += c[i - ];
for(int i = ; i <= sz; ++i) a[c[t[i].val]--] = i;
for(int i = sz; i; --i) f[t[a[i]].par] += f[a[i]];
for(int i = ; i <= sz; ++i) fa[i][] = t[i].par;
for(int j = ; j <= ; ++j)
for(int i = ; i <= sz; ++i)
fa[i][j] = fa[fa[i][j - ]][j - ]; S[] = '-';
for(int i = ; i <= n; ++i)
{
S[++len] = '#';
S[++len] = s[i]; }
S[++len] = '#';
S[++len] = '+';
for(int i = ; i <= len; ++i)
{
if(i < mx) p[i] = min(mx - i, p[ * pos - i]);
while(S[i - p[i]] == S[i + p[i]])
{
ans = max(ans, 1LL * p[i] * query((i - p[i] + ) >> , (i + p[i]) >> ));
++p[i];
}
if(i + p[i] > mx)
{
pos = i;
mx = i + p[i];
}
}
printf("%lld\n", ans);
return ;
}

最新文章

  1. C语言 完美字符串
  2. 【原】关于使用sklearn进行数据预处理 —— 归一化/标准化/正则化
  3. Java特性-动态代理
  4. Android开发跳槽、简历和面试的那些事
  5. Python 编程规范-----转载
  6. 1388 - Graveyard(数论)
  7. CSS 解决&lt;td&gt;里面内容太多把表格弄变形的原因,设置 自动换行。
  8. Chrome下的语音控制框架MyVoix.js使用篇(二)
  9. Android使用Home键后应用程序重启的问题
  10. 【java学习】Servlet简单的表单程序(一)
  11. 安卓 ArrayList,LinkedList,HashSet,Vector,TreeSet的区别和使用
  12. Easyui 实现点击不同树节点打开不同tab页展示不同datagrid表数据设计
  13. 冰水挑战 HDU - 6495
  14. python 基础之python的六大标准数据类型
  15. eclipse中maven项目jar包不会自动下载解决办法
  16. redis踩坑记录
  17. [国家集训队] calc
  18. MATLAB总结二
  19. 最长子回文字符串(Manacher’s Algorithm)
  20. sqlserver 抓取所有执行语句 SQL语句分析 死锁 抓取

热门文章

  1. pwm驱动原理和代码实现
  2. 搭建windows下的odoo开发环境
  3. Irrlicht 3D Engine 笔记系列之 教程4 - Movement
  4. JavaScript闭包其一:闭包概论 函数式编程中一些基本定义
  5. MyEclipse 设置智能提示
  6. 安卓UI适配限定符
  7. windows下route命令详解(转载)
  8. 说说设计模式~单件模式(Singleton)
  9. xcode升级到6.0以后遇到的警告错误 原帖链接http://www.cocoachina.com/bbs/simple/?t112432.html
  10. unity 接触一个月的感受和心得