Manacher算法详解与应用实战
Manacher算法核心思想
Manacher算法是一种在线性时间复杂度O(n)内求解字符串最大回文子串长度的高效算法。其核心在于通过在原字符串中插入特殊分隔符，将所有回文问题统一转化为奇数长度回文的处理，并利用已知回文的对称性来加速计算。
构造扩展字符串
将原字符串每个字符之间插入一个特殊符号（如'#'），并在首尾添加边界标记（如'$'），形成新串。例如：
原串: "abc" 新串: "$#a#b#c#"
这样可确保所有回文中心均为奇数下标，且避免了偶数长度回文的复杂判断。
算法实现逻辑
维护两个关键变量：right 表示当前已处理范围内最远延伸位置，id 为该回文中心下标。对于每个位置 i，若其位于已有回文范围内，则可利用对称性快速初始化半径；否则从0开始扩展。
代码实现（以HDU 3068为例）
const int MAXN = 110005;
char original[MAXN], expanded[MAXN * 2];
int radius[MAXN * 2];
int solve() {
char line[MAXN];
while (scanf("%s", line) == 1) {
int len = strlen(line);
// 构造扩展串
expanded[0] = '$';
expanded[1] = '#';
for (int i = 0; i < len; ++i) {
expanded[i * 2 + 2] = line[i];
expanded[i * 2 + 3] = '#';
}
int n = len * 2 + 2;
expanded[n] = '\0';
int rightmost = 0, center = 0;
radius[0] = 0;
for (int i = 1; i < n; ++i) {
if (i < rightmost) {
radius[i] = std::min(radius[center * 2 - i], rightmost - i);
} else {
radius[i] = 0;
}
// 向外扩展回文
while (expanded[i + radius[i] + 1] == expanded[i - radius[i] - 1]) {
++radius[i];
}
// 更新最远扩展位置和中心
if (i + radius[i] > rightmost) {
rightmost = i + radius[i];
center = i;
}
}
int maxLen = 0;
for (int i = 0; i < n; ++i) {
maxLen = std::max(maxLen, radius[i]);
}
printf("%d\n", maxLen);
}
return 0;
}进阶应用：HDU 3294 的字符变换处理
该题不仅要求找出最长回文子串，还需将其转换为特定字母映射规则下的输出结果。关键是根据回文中心与半径还原原始位置，并进行循环移位编码。
int main() {
char input[200005];
while (gets(input)) {
int len = strlen(input);
// 构建扩展串
expanded[0] = '$';
expanded[1] = '#';
for (int i = 2; i < len; ++i) {
expanded[i * 2 - 2] = input[i];
expanded[i * 2 - 1] = '#';
}
int n = len * 2 - 2;
expanded[n] = '\0';
int rightmost = 0, center = 0;
radius[0] = 0;
for (int i = 1; i < n; ++i) {
if (i < rightmost) {
radius[i] = std::min(radius[center * 2 - i], rightmost - i);
} else {
radius[i] = 0;
}
while (expanded[i + radius[i] + 1] == expanded[i - radius[i] - 1]) {
++radius[i];
}
if (i + radius[i] > rightmost) {
rightmost = i + radius[i];
center = i;
}
}
int maxRad = 0, midIdx = 0;
for (int i = 1; i < n; ++i) {
if (radius[i] > maxRad) {
maxRad = radius[i];
midIdx = i;
}
}
if (maxRad <= 1) {
puts("No solution!");
continue;
}
int start = (midIdx - maxRad + 1) / 2 + 1;
printf("%d %d\n", start - 2, start - 2 + maxRad - 1);
for (int i = 0; i < maxRad; ++i) {
char c = input[start + i];
c = c - 'a' + 'A'; // 转大写
c = (c - 'A' + 13) % 26 + 'A'; // ROT13 加密
printf("%c", c);
}
puts("");
}
return 0;
}