A1280. 最长双回文串
2024-10-11 23:00:25
学习了回文树,地址: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 ;
}
最新文章
- phpstorm 63342默认端口怎么修改
- Mob.com 短信验证的简单使用
- 小米手机与魅族的PK战结果 说明了什么
- java发布项目后注意小点,以及对于金额在java中的处理
- 控制流之break
- 201521123060 《Java程序设计》第6周学习总结
- 【已解决】checkout 配置无效的问题可以进来看下
- 了解unix操作系统发展阶段
- Python爬虫之自制英汉字典
- 洛谷P4563 [JXOI2018]守卫(dp)
- Performance Tuning MySQL
- Spring框架之使用JdbcTemplate开发Dao层程序
- 20165228 2017-2018-2《Java程序设计》课程总结
- Java关键字解释及作用
- HTML5 defer和async的区别
- 【翻译自mos文章】在RHEL7/OL7上安装Oracle 12.1.0.2的server端或者client时,报须要&;quot;compat-libstdc++&;quot;包
- LoadRunner如何获得参数化中每个关键字的搜索响应时间
- nyoj-----D的小L
- 关于Unity中UI中的Slider,Toggle和InputField等节点
- C++模板中的嵌套
热门文章
- Variables多种表达
- 62.纯 CSS 创作一只蒸锅(感觉不好看呀)
- java细节知识
- leetcode94
- 深度学习原理与框架-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)
- Python程序互斥体
- 零基础爬虫----python爬取豆瓣电影top250的信息(转)
- win10系统goole浏览器安装postMan插件
- WMS常用表
- POJ-2253.Frogger.(求每条路径中最大值的最小值,最短路变形)