今天打算补前晚 BC 的第二题，发现要用到能在 O(n) 时间求最大回文子串长度的 Manacher 算法，第一次听，于是便去百度了下，看了大半天，总算能看懂了其思想，至于他给出的代码模板我没能完全看懂，只好自己试着实现，发现理解了思想后还是能实现出来的，用自己的风格去写更好理解，先附上讲解 Manacher 算法的几个链接：
Manacher算法--O（n）回文子串算法 （我就是看这个理解的~）
hdu 3068 正好是裸题，我便试着写下，我是这样子构造新串的：
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 ;
}