51nod 1089最长回文子串V2 (manacher)
2024-09-02 22:57:11
经典题
manacher是一种很神奇的算法,
算是动态规划的一种,不过利用的信息非常有效
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + ;
char S2[maxn*], str[maxn*];
int R[maxn*];
void Manacher(char* S){
int L = strlen(S);
for(int i = , j = ; i < *L; i += , j += ) S2[i] = '#', S2[j] = S[j/];
S2[*L] = '#';
int mx = -, id = -;
for(int i = ; i < *L; i++){
R[i] = mx-i >= ? min(R[*id-i], mx-i+) : ;
while(i+R[i] <= *L && S2[i+R[i]] == S2[i-R[i]]) R[i]++;
if(i+R[i]- > mx) mx = i+R[i]-, id = i;
}
} int main()
{
cin>>str;
Manacher(str);
int L = strlen(str), ans = ;
//for(int i = 0; i < 2*L; i++) cout<<R[i]<<" "; cout<<endl;
for(int i = ; i < *L; i += ) ans = max(ans, *(R[i]/-) + );
for(int i = ; i < *L; i += ) ans = max(ans, R[i]-);
cout<<ans<<endl;
return ;
}
最新文章
- log4net 记录MVC监控日志
- 1Z0-053 争议题目解析706
- iOS地图 -- 地理编码和反地理编码
- leetcode 186. Reverse Words in a String II 旋转字符数组 ---------- java
- Json的序列化与反序列化
- web基础
- W3C对DOM2.0定义的标准事件
- Storyboards
- DSP using MATLAB 示例Example3.22
- Java内存分配和内存管理
- 《javascript高级程序设计》 第25章 新兴的API
- 函数rec_get_nth_field_offs_old
- C语言字节对齐
- 【树形动态规划】【CTSC1997】选课 解题报告
- Date与Calendar
- WEB打印插件jatoolsPrinter
- Vue引入elementUI组件全过程
- 26_ArrayList_HashSet的比较及Hashcode分析
- Qt532.QString_填充字符
- Java 枚举(enum) 详解4种常见的用法