【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=3068

【算法】

Manacher算法求最长回文子串

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 110010 char s[MAXN]; inline void Manacher()
{
int i,len,ans = ,pos = ,mx = ;
static char tmp[MAXN<<];
static int p[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;
}
}
for (i = ; i <= len; i++) ans = max(ans,p[i]-);
printf("%d\n",ans);
} int main()
{ while (scanf("%s",s+) != EOF) Manacher(); return ; }

最新文章

  1. Java常量的应用
  2. gradle下载地址
  3. Java并发之BlockingQueue 阻塞队列(ArrayBlockingQueue、LinkedBlockingQueue、DelayQueue、PriorityBlockingQueue、SynchronousQueue)
  4. iOS GET、POST数据解析
  5. bzoj4165: 矩阵
  6. eclipse中的工程中有叉叉
  7. hdu 4374 单调队列优化动态规划
  8. CentOS快捷键总结
  9. DB2 “The transaction log for the database is full” 存在的问题及解决方案
  10. cpanel导入大数据库(mysql)的方法
  11. WinRAR5.01注册码附注册机
  12. 动态添加Redis密码认证
  13. PS 软件操作应用处理——粒子化任务效果
  14. 九九乘法表.py
  15. jboss7开发配置指南
  16. 无法添加注解@Resource
  17. 移动端跨平台方案对比:React Native、weex、Flutter
  18. visual studio 2013 几个测试工具(Nunit 3、xUnit)
  19. json-lib和dom4j实现JSON转XML
  20. python脚本难点

热门文章

  1. Java怎么实现文件数据拷贝
  2. 13Microsoft SQL Server SQL 高级事务,锁,游标,分区
  3. 在TWaver的Tree节点上画线
  4. Redis多实例配置以及主从同步
  5. JDBC插入数据时中文变为问号的解决方法
  6. 长久不用的mysql报错ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/tmp/mysql.sock&#39; (2)
  7. springcloud(十三):Ribbon客户端负载均衡实例
  8. ISO7220M芯片调试总结
  9. java 访问对象私有变量
  10. 解决Windows Server 2012 R2 Datacenter云服务器无法运行opencv python程序的问题