最长双回文串(模板+dp)
2024-10-02 01:58:36
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
int x = , f = ; char ch = getchar();
while(ch > '' || ch < ''){if (ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){ x = x*+ch-''; ch = getchar();}
return x*f;
} /************************************************************************/ const int maxn = 1e6+;
char s[maxn];
char str[maxn];
int dp1[maxn], p[maxn];
int dp2[maxn];
int len; void manacher(char s[], int len){
int ans = ;
for(int i = ;i <= len;i++){
str[i<<] = s[i];
str[(i<<)+] = '#';
}
str[] = '#'; str[len*+] = '#';
str[] = '&'; str[len*+] = '$';
len = len*+;
int j = , k;
for(int i = ;i <= len;){
while(str[i-j-] == str[i+j+]) j++;
p[i] = j;
if(j > ans) ans = j;
for(k = ;k <= j && (p[i]-k != p[i-k]);k++){
p[i+k] = min(p[i-k], p[i] - k);
}
i += k;
j = max(j-k, );
}
} int main(){
scanf("%s", s+);
len = strlen(s+);
manacher(s, len);
len = len*+;
cout << "str: " << str << endl;
for(int i = ;i <= len;i++){
for(int j = p[i];j >= ;j--){
if(dp1[i+j] >= j) break;
dp1[i+j] = j;
}
for(int j = p[i];j >= ;j--){
if(dp2[i-j] >= j) break;
dp2[i-j] = j;
}
}
int ans = ;
for(int i = ;i <= len-;i++){
if(dp1[i] && dp2[i])
ans = max(ans, dp1[i] + dp2[i]);
}
cout << ans << endl;
return ;
}
最新文章
- virtualbox安装增强功能时【未能加载虚拟光盘】
- sql server 2005导出数据到oracle
- sax解析原理与案例
- C#小数点位数处理方法
- GitHub上非常受开发者欢迎的iOS开源项目(二)
- JS报表打印分页CSS
- Python中协程的实现
- mongodb Enable Auth
- React 中的this.setState
- 七层协议&;网络配置
- MSSQL 如何采用sql语句 获取建表字段说明、字段备注、字段类型、字段长度
- urllib的实现---请求响应and请求头处理
- [树链剖分]hihocoder1883
- windows server r2 安装vs2017 更新补丁Windows8.1-KB2919355-x6
- SpringMVC之JSON交互
- 关于linux下自定义的 alias文件和自定义函数库的通用写法(只适合自己的)
- kraken-ejs创建一个项目【学习札记】
- mysql 俩个时间相减后取分钟
- 黄聪:C#使用能够foreach对hashtable、List遍历时“集合已修改;可能无法执行枚举操作。”错误
- 持续集成与devops
热门文章
- 【leetcode刷题笔记】Validate Binary Search Tree
- [转]七个对我最好的职业建议(精简版)--Nicholas C. Zakas
- JS通过经纬度计算两个地方的距离
- 洛谷【P3612】[USACO17JAN]Secret Cow Code秘密奶牛码
- Poj 1401 Factorial(计算N!尾数0的个数——质因数分解)
- myeclipse保存时弹出Building workspace
- Java常见设计模式之单例模式
- char与wchar_t数据类型
- oop的方式来操纵时间
- C++模板特化编程