1089 最长回文子串 V2(Manacher算法)
2024-10-19 00:21:40
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题
收藏
关注
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str,输出Str里最长回文子串的长度。
Input
输入Str(Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
相关问题
最长回文子串
0
回文串划分 V2
640
回文串划分
40
回文字符串
10
//O(n) manacher算法
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e6+;
int l,len,p[N<<];
char s[N],S[N<<];
void manacher(){
int ans=,id=,mx=-;
for(int i=;i<l;i++){
if(id+mx>i) p[i]=min(p[id*-i],id+mx-i);
while(i-p[i]->=&&i+p[i]+<=l&&S[i-p[i]-]==S[i+p[i]+]) p[i]++;
if(id+mx<i+p[i]) id=i,mx=p[i];
ans=max(ans,p[i]);
}
printf("%d\n",ans);
}
int main(){
scanf("%s",s);len=strlen(s);
l=-;
for(int i=;i<len;i++) S[++l]='#',S[++l]=s[i];
S[++l]='#';
manacher();
return ;
}
//O(nlogn) 字符串哈希
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef int i64;
const int N=1e6+;
int n,m,ans,a[N];char s[N];
i64 P,pow[N],hash_l[N],hash_r[N];
void get_hash(){
pow[]=;
for(int i=;i<=m;i++) pow[i]=pow[i-]*P;
for(int i=;i<=m;i++) hash_r[i]=hash_r[i-]*P+a[i];
for(int i=m;i>=;i--) hash_l[i]=hash_l[i+]*P+a[i]; }
int main(){
P=;
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++){
a[++m]='#';
a[++m]=s[i]-'A';
}
a[++m]='#';
get_hash();
int l,r,mid;
for(int i=;i<=m;i++){
l=;
if(i-<m-i) r=i;
else r=m-i+;
while(r-l>){
mid=l+r>>;
i64 hash_to_l=hash_r[i-]-hash_r[i-mid-]*pow[mid];
i64 hash_to_r=hash_l[i+]-hash_l[i+mid+]*pow[mid];
if(hash_to_l==hash_to_r) l=mid;
else r=mid;
}
ans=max(ans,l);
}
printf("%d",ans);
return ;
}
最新文章
- 转:Java中abstract和interface的区别
- MySQL 5.1 参考手册CHM (官方 简体中文版)
- Android笔记:去除标题栏
- 从零开始学JAVA(06)-WebService_Jersey_Restful
- IE6中position:fixed无效问题解决
- Memcache缓存与Mongodb数据库的优势和应用
- Redis指令文档
- ios专题 - 异步下载加下载进度显示
- AndroidStudio中 R文件缺失的办法
- DataTables在回调方法中使用api
- 对XSD schema文件中elementFormDefault属性的理解
- python webserver, based on SimpleHTTPServer
- Python内存优化
- Python中的选择排序
- Android Firebase 服务简介
- Django 实现list页面检索
- MyEclipes相关配置
- Mac使用Clion配置OpenGL
- manjaro 配置 独立显卡驱动
- 爬虫scrapy的使用
热门文章
- python基础之面向对象高级编程
- ahjesus HttpQuery
- AbstractFactoryPattern(抽象工厂)
- CS.动态加载DLL.动态生成.运行代码.BS.AutoFac管理实现类
- Linux下清理内存和Cache方法 /proc/sys/vm/drop_caches
- Code First :使用Entity. Framework编程(6) ----转发 收藏
- elasticsearch GIS空间查询问题解决
- Linux SSH登录慢案例分析
- mysql数据库乱码解决方法之一
- Linux脚本学习