Manacher 算法(hdu 3068 && hdu 3294)

时间:2021-05-14 00:25:38

  今天打算补前晚 BC 的第二题,发现要用到能在 O(n) 时间求最大回文子串长度的 Manacher 算法,第一次听,于是便去百度了下,看了大半天,总算能看懂了其思想,至于他给出的代码模板我没能完全看懂,只好自己试着实现,发现理解了思想后还是能实现出来的,用自己的风格去写更好理解,先附上讲解 Manacher 算法的几个链接:

  Manacher算法--O(n)回文子串算法 (我就是看这个理解的~)

  Manacher算法处理字符串回文

  hdu3068之manacher算法+详解

  浅谈manacher算法

  hdu 3068 正好是裸题,我便试着写下,我是这样子构造新串的:

Manacher 算法(hdu 3068 && hdu 3294)

  hdu 3068 代码如下:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ; // str 为原串, s 为新串
char str[N], s[N << ];
int p[N << ];
// p[i] 表示以 s[i] 为中心时的回文半径,不包括 p[i]
// 即若 s[i - 1] != s[i + 1] 时,p[i] = 0; int main() {
while(~scanf("%s",str)) {
int n = strlen(str);
s[] = '$'; // 构造新串
s[] = '#';
for(int i = ; i < n; ++i) {
s[i * + ] = str[i]; // 下标要处理好
s[i * + ] = '#';
}
n = n * + ; // 更新新串的长度
s[n] = '\0'; // 最后的结束符别忘了 // right 记录的是在 i 之前的回文串中,某个回文串延伸至最右端的位置
// id 就是该回文串的下标(注意都是在新串中的)
int right = , id = ;
p[] = ;
// 因为是 s[0] == '$',作为特殊标记,左右两边都没有相等的,所以初始化为 0,
// 同理 right 一开始能延伸到的位置就是 s[0] 的位置,也就是 0,id 当然也为 0 // 主算法要开始了
for(int i = ; i < n; ++i) {
if(right > i)
p[i] = min(p[ * id - i], right - i);
else p[i] = ;
while(s[i + p[i] + ] == s[i - p[i] - ]) ++p[i];
if(i + p[i] > right) {
right = i + p[i];
id = i;
}
} // printf("\n下标: ");
// for(int i = 0; i <= n; ++i)
// printf("%d ",i);
// puts("");
// printf("新串: ");
// for(int i = 0; i < n; ++i)
// printf("%c ",s[i]);
// printf(" \\0\np[i]: ");
// for(int i = 0; i < n; ++i)
// printf("%d ",p[i]);
// puts(""); int ans = ;
for(int i = ; i < n; ++i)
ans = max(ans, p[i]); // p[i] 就是原串中的回文长度, 无须作任何 +1、-1
printf("%d\n",ans);
}
return ;
}

  还有一题也是需要用到这个算法的,hdu 3294,只是对于最后的结果输出需要处理一下,恶心的模拟,直接贴代码了:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ; char str[N], s[N << ];
int p[N << ]; int main() {
while(gets(str)) {
int n = strlen(str);
s[] = '$';
s[] = '#';
for(int i = ; i < n; ++i) {
s[i * - ] = str[i];
s[i * - ] = '#';
}
n = n * - ;
s[n] = '\0'; int right = , id = ;
p[] = ;
for(int i = ; i < n; ++i) {
if(right > i)
p[i] = min(p[id * - i], right - i);
else p[i] = ;
while(s[i + p[i] + ] == s[i - p[i] - ]) ++p[i];
if(i + p[i] > right) {
right = i + p[i];
id = i;
}
}
int Max = , mid;
for(int i = ; i < n; ++i) {
if(p[i] > Max) {
Max = p[i];
mid = i;
}
}
if(Max == ) {
puts("No solution!");
continue;
} int strid = (mid - Max + ) / + ;
printf("%d %d\n", strid - , strid - + Max - ); for(int i = ; i < Max; ++i) {
char ch = str[strid + i] + ('a'- str[]);
if(ch < 'a') ch = 'z' + - ('a' - ch);
else if(ch > 'z') ch = 'a' - + (ch - 'z');
printf("%c",ch);
}
puts("");
}
return ;
}