【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2565

【算法】

Manacher

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ; char s[MAXN]; inline void Manacher()
{
int i,pos = ,mx = ,len,ans = ;
static char tmp[MAXN<<];
static int p[MAXN<<],l[MAXN<<],r[MAXN<<];
len = strlen(s+);
for (i = ; i <= len; i++)
{
tmp[*i-] = '#';
tmp[*i] = s[i];
}
tmp[len = * len + ] = '#';
for (i = ; i <= len; i++)
{
if (mx > i) p[i] = min(p[*pos-i],mx-i);
else p[i] = ;
while (i - p[i] >= && i + p[i] <= len && tmp[i-p[i]] == tmp[i+p[i]]) p[i]++;
if (i + p[i] - > mx)
{
mx = i + p[i] - ;
pos = i;
}
}
pos = ;
for (i = ; i <= len; i++)
{
if (tmp[i] == '#')
{
while (pos + p[pos] < i) pos++;
l[i] = i - pos;
}
}
pos = len;
for (i = len; i >= ; i--)
{
if (tmp[i] == '#')
{
while (pos - p[pos] > i) pos--;
r[i] = pos - i;
}
}
for (i = ; i <= len; i++) ans = max(ans,l[i]+r[i]);
printf("%d\n",ans);
} int main()
{ scanf("%s",s+);
Manacher(); return ; }

最新文章

  1. 转载文章——从HelloWorld学习操作系统
  2. ZOJ 3703 Happy Programming Contest
  3. 错误-spring3.2的架构在tomcat6.0中无法正常启动,抛出java.lang.NoClassDefFoundError: javax/servlet/AsyncListener
  4. TypeError: &#39;bases&#39; is null or not an object。IE8 bug 腐朽的对象
  5. C# 根据包含文件的路径和文件的名称的字符串获取文件名称的几种方法
  6. Microsoft Dynamics CRM 2013 CD-KEY
  7. [CentOS]yum安装postgres和ntfs-3g
  8. CSS3--幽灵按钮特效(实例)
  9. 人工智能起步-反向回馈神经网路算法(BP算法)
  10. 汽车行业的DMS系统 IT不变应万变
  11. Geogebra里给带有曲线和直线混合边界的封闭区域填充颜色
  12. shell 验证ip
  13. windows server 2008 应用程序池自动关闭 C:\Windows\system32\RpcProxy\RpcProxy.dll failed to load
  14. 201521123111《Java程序设计》第10周学习总结
  15. python3抓图学习-百度贴吧
  16. 配置STP、RSTP以及负载均衡
  17. xcodebuild构建时报错unknown error -1=ffffffffffffffff Command /bin/sh failed with exit code 1
  18. 【知名的移动APP和网站设计工具】Sketch for Mac 54.1
  19. [C]内存管理、内存泄露、堆栈
  20. 06 - JavaSE之常用类

热门文章

  1. https Full Handshake
  2. VBA中Option的四种用法
  3. 微信小程序获取二维码并把logo替换为自己的头像
  4. 微信 之jsapi实现支付
  5. 我的FPGA
  6. POJ3984——迷宫问题
  7. 51nod1006 -最长公共子序列Lcs【动态规划】
  8. 网络编程:tcp、udp、socket、struct、socketserver
  9. Git 基础教程 之 别名
  10. Maven学习总结(十一)——Maven项目对象模型pom.xml文件详解