基准时间限制: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 ;
}

 

最新文章

  1. 转:Java中abstract和interface的区别
  2. MySQL 5.1 参考手册CHM (官方 简体中文版)
  3. Android笔记:去除标题栏
  4. 从零开始学JAVA(06)-WebService_Jersey_Restful
  5. IE6中position:fixed无效问题解决
  6. Memcache缓存与Mongodb数据库的优势和应用
  7. Redis指令文档
  8. ios专题 - 异步下载加下载进度显示
  9. AndroidStudio中 R文件缺失的办法
  10. DataTables在回调方法中使用api
  11. 对XSD schema文件中elementFormDefault属性的理解
  12. python webserver, based on SimpleHTTPServer
  13. Python内存优化
  14. Python中的选择排序
  15. Android Firebase 服务简介
  16. Django 实现list页面检索
  17. MyEclipes相关配置
  18. Mac使用Clion配置OpenGL
  19. manjaro 配置 独立显卡驱动
  20. 爬虫scrapy的使用

热门文章

  1. python基础之面向对象高级编程
  2. ahjesus HttpQuery
  3. AbstractFactoryPattern(抽象工厂)
  4. CS.动态加载DLL.动态生成.运行代码.BS.AutoFac管理实现类
  5. Linux下清理内存和Cache方法 /proc/sys/vm/drop_caches
  6. Code First :使用Entity. Framework编程(6) ----转发 收藏
  7. elasticsearch GIS空间查询问题解决
  8. Linux SSH登录慢案例分析
  9. mysql数据库乱码解决方法之一
  10. Linux脚本学习