学习了回文树,地址:http://blog.csdn.net/u013368721/article/details/42100363;

这个题就是正这反着加一遍就好,一开始我想的是枚举每个位置,然后一直按fail跳,再接上跳完的位置的len,后来想了不行,一个很长的全是a的串就可以卡成n^2。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=;
int m,len[maxn],n,nxt[maxn][],fail[maxn],last,now,ss[maxn],tot,res[maxn],ans;
char s[maxn];
int getfail(int x){
while(ss[m-len[x]-]!=ss[m])x=fail[x];
return x;
}
int add(char c){
int x=c-'a';
ss[++m]=x;
int cur=getfail(last);
if(!nxt[cur][x]){
len[tot]=len[cur]+;
fail[tot]=nxt[getfail(fail[cur])][x];
nxt[cur][x]=tot;
++tot;
}
last=nxt[cur][x];
return len[last];
}
void init(){
memset(nxt,,sizeof(nxt));
fail[]=;len[]=;
len[]=-;last=;tot=;
ss[]=-;m=;
}
int main(){
scanf("%s",s+);n=strlen(s+);
init();for(int i=;i<=n;++i){res[i]=add(s[i]);}
init();for(int i=n;i>=;--i){ans=max(ans,add(s[i])+res[i-]);}
cout<<ans;
return ;
}

最新文章

  1. phpstorm 63342默认端口怎么修改
  2. Mob.com 短信验证的简单使用
  3. 小米手机与魅族的PK战结果 说明了什么
  4. java发布项目后注意小点,以及对于金额在java中的处理
  5. 控制流之break
  6. 201521123060 《Java程序设计》第6周学习总结
  7. 【已解决】checkout 配置无效的问题可以进来看下
  8. 了解unix操作系统发展阶段
  9. Python爬虫之自制英汉字典
  10. 洛谷P4563 [JXOI2018]守卫(dp)
  11. Performance Tuning MySQL
  12. Spring框架之使用JdbcTemplate开发Dao层程序
  13. 20165228 2017-2018-2《Java程序设计》课程总结
  14. Java关键字解释及作用
  15. HTML5 defer和async的区别
  16. 【翻译自mos文章】在RHEL7/OL7上安装Oracle 12.1.0.2的server端或者client时,报须要&amp;quot;compat-libstdc++&amp;quot;包
  17. LoadRunner如何获得参数化中每个关键字的搜索响应时间
  18. nyoj-----D的小L
  19. 关于Unity中UI中的Slider,Toggle和InputField等节点
  20. C++模板中的嵌套

热门文章

  1. Variables多种表达
  2. 62.纯 CSS 创作一只蒸锅(感觉不好看呀)
  3. java细节知识
  4. leetcode94
  5. 深度学习原理与框架-Tensorboard可视化展示(代码) 1.tf.reuse_default_graph(进行结构图的重置) 2.tf.summary.FileWriter(writer实例化) 3. write.add_graph(graph的写入) 4. tf.summary.merge_all(将summary进行合并) 5.write.add_summary(将所有summary)
  6. Python程序互斥体
  7. 零基础爬虫----python爬取豆瓣电影top250的信息(转)
  8. win10系统goole浏览器安装postMan插件
  9. WMS常用表
  10. POJ-2253.Frogger.(求每条路径中最大值的最小值,最短路变形)