【HDU 3068】 最长回文
2024-08-31 00:40:24
【题目链接】
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 ; }
最新文章
- Java常量的应用
- gradle下载地址
- Java并发之BlockingQueue 阻塞队列(ArrayBlockingQueue、LinkedBlockingQueue、DelayQueue、PriorityBlockingQueue、SynchronousQueue)
- iOS GET、POST数据解析
- bzoj4165: 矩阵
- eclipse中的工程中有叉叉
- hdu 4374 单调队列优化动态规划
- CentOS快捷键总结
- DB2 “The transaction log for the database is full” 存在的问题及解决方案
- cpanel导入大数据库(mysql)的方法
- WinRAR5.01注册码附注册机
- 动态添加Redis密码认证
- PS 软件操作应用处理——粒子化任务效果
- 九九乘法表.py
- jboss7开发配置指南
- 无法添加注解@Resource
- 移动端跨平台方案对比:React Native、weex、Flutter
- visual studio 2013 几个测试工具(Nunit 3、xUnit)
- json-lib和dom4j实现JSON转XML
- python脚本难点
热门文章
- Java怎么实现文件数据拷贝
- 13Microsoft SQL Server SQL 高级事务,锁,游标,分区
- 在TWaver的Tree节点上画线
- Redis多实例配置以及主从同步
- JDBC插入数据时中文变为问号的解决方法
- 长久不用的mysql报错ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/tmp/mysql.sock&#39; (2)
- springcloud(十三):Ribbon客户端负载均衡实例
- ISO7220M芯片调试总结
- java 访问对象私有变量
- 解决Windows Server 2012 R2 Datacenter云服务器无法运行opencv python程序的问题