HDU 3068 回文串--Manacher
-- HDU 回文 Manacher
2023-09-11 14:20:13 时间
//2009 Multi-University Training Contest 16 - Host by NIT //最长回文 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100000 + 10; char Ma[maxn*2]; int Mp[maxn*2]; void Manacher(char s[],int len) { int l=0; Ma[l++]='$'; Ma[l++]='#'; for(int i=0;i<len;i++) { Ma[l++]=s[i]; Ma[l++]='#'; } Ma[l]=0; int mx=0,id=0; for(int i=0;i<l;i++) { Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++; if(i+Mp[i]>mx) { mx=i+Mp[i]; id=i; } } } char s[maxn]; int main() { while(~scanf("%s",s)) { int len=strlen(s); Manacher(s,len); int ans=0; for(int i=0;i<2*len+2;i++) ans=max(ans,Mp[i]-1); printf("%d\n",ans); } return 0; }
相关文章
- 01- Shell脚本学习--入门
- Vsftpd 2.2.x安装和配置--centos7前的版本
- Java -- JDBC 学习--处理Blob
- JAVA编程思想读书笔记(四)--对象的克隆
- redis单机搭建--详细
- java多线程 -- ConcurrentHashMap 锁分段 机制
- [Function Programming] Function modelling -- 9. Monad Transformers
- [Node.js] Broswerify -- 1
- PHP连接MySQL数据库的三种方式(mysql、mysqli、pdo)--续
- npm install --save 、--save-dev 、-D、-S的区别详细解说
- AI开发者大会:2020年7月3日09:30--09:50司罗《为商业搭建语言桥梁》
- 云小课|打造企业数据“高内聚,低耦合”--试试GaussDB(DWS)逻辑集群,实现数据物理隔离
- y127.第七章 服务网格与治理-Istio从入门到精通 -- EnvoyFilter(十三)
- 3D数学--学习笔记(五岁以下儿童):总结一些概念(避免遗忘!)
- 龙芯软件开发(16)-- 内存参数读取
- 程序员修神之路--redis做分布式锁可能不那么简单
- 《深度学习》李宏毅 -- task2 回归