题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3068

题意:给你一个字符串,让你求最长的回文子串。

题解:数据量比较大,暴力O(n2)会超时,直接上马拉车,模版题。

 #include<cstdio>
#include<cstring>
#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)
const int maxn = ;//字符串长度
struct Manacher{
char str[maxn<<];
int p[maxn<<],len,mx,id,tl,ans,i;
//bool pre[maxn],suf[maxn];//前(后)缀(前(后)p[i]-1个字符)是回文串
//void init(int len){for(int i=0;i<=len;i++)suf[i]=0,pre[i]=0;}
int maxlen(char *s){
len=strlen(s),mx=,id=,tl=,str[tl++]='$',str[tl++]='#';
for(i=;i<len;i++)str[tl++]=s[i],str[tl++]='#';
for(i=,str[tl]=,ans=;i<tl;i++){
p[i]=mx>i?min(p[(id<<)-i],mx-i):;
while(str[i-p[i]]==str[i+p[i]])p[i]++;
if(i+p[i]>mx)mx=i+p[i],id=i;
ans=max(ans,p[i]);
//if(i-p[i]==0)pre[p[i]-1]=true;
//if(i+p[i]==len*2+2)suf[p[i]-1]=true;
}
return ans-;
}
}M;
char s[maxn];
int main(){
while(~scanf("%s",s)){
printf("%d\n",M.maxlen(s));
}
return ;
}

最新文章

  1. 如何一步一步用DDD设计一个电商网站(七)—— 实现售价上下文
  2. Java程序员岗位
  3. Java学习
  4. Mono addin 学习笔记 1
  5. C与Python变量的区别
  6. 遇见了这个问题:App.config提示错误“配置系统未能初始化”
  7. hibernate映射文件基础
  8. ListView开发笔记
  9. 安装虚拟机时出现The Microsoft Runtime DLL
  10. Mysql主从配置+读写分离(转)
  11. [翻译]初识SQL Server 2005 Reporting Services Part 2
  12. PostgreSQL 配置安装
  13. Gradle笔记——关于Gradle 1.12
  14. 创建Windows服务
  15. Mac各种数据库安装和启动【笔记】
  16. UI自动化(九)Css Selector
  17. Python — 字典dict 和 集合set
  18. 12.double的int方
  19. Maven学习--- 搭建多模块企业级项目
  20. 关于.Net开源并跨平台的思考

热门文章

  1. 验证码计时 -- UIButton setTitle 闪烁问题解决方案
  2. C++虚函数继承的bug
  3. zoj 2913 Bus Pass
  4. Paint on a Wall
  5. spring杂记
  6. Spring的Bean之Bean的基本概念[转]
  7. java web应用程序目录
  8. c# socket传输struct类型
  9. jQuery 截取double数据 重新赋值
  10. hdu_4918_Query on the subtree(树的分治+树状数组)