HDU 3294 Girls' Research —— Manacher 算法求最長回文子串（字符映射變體）

HDU 3294：給定一個字符 ch 代表真正的 'a'，即字符表循環偏移。將輸入字串按偏移映射為真實字串，再求長度 ≥ 2 的最長回文子串，輸出起終位置（原串下標）與回文內容。多組測試，字串長 ≤ 200,000。

一、字符映射

int shift = ch - 'a'; // 例如 'b' -> 1
for (int i = 0; s[i]; ++i)
    s[i] = 'a' + (s[i] - 'a' + shift) % 26;

二、Manacher 算法 O(n) 求最長回文

預處理插入 # 統一奇偶長度：$ # a # b # a # @。
維護 p[i] = 以 i 為中心的回文半徑（含中心）。
核心變量：mx 當前最右達到位置，id 對應中心。
利用對稱性 p[i] = min(p[2*id-i], mx-i) 初始化，再暴力擴展。

三、關鍵代碼

void manacher() {
    int mx = 0, id = 0, maxLen = 0, center = 0;
    for (int i = 1; str[i]; ++i) {
        if (mx > i) p[i] = min(p[2*id - i], mx - i);
        else p[i] = 1;
        while (str[i - p[i]] == str[i + p[i]]) ++p[i];
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        if (p[i] > maxLen) { maxLen = p[i]; center = i; }
    }
    // maxLen 包含中心和 #，實際回文長度 = maxLen - 1
    // 原串下標：(center - maxLen) / 2  到  (center + maxLen - 2) / 2
}

四、完整 AC 代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400010; // 2*n+5
char str[MAXN], s[MAXN];
int p[MAXN];

int main() {
    char ch;
    while (scanf("%c%s", &ch, s) == 2) {
        getchar(); // 吃掉換行
        int shift = ch - 'a';
        for (int i = 0; s[i]; ++i)
            s[i] = 'a' + (s[i] - 'a' + shift) % 26;

        // 預處理
        int len = 0;
        str[len++] = '$'; str[len++] = '#';
        for (int i = 0; s[i]; ++i) {
            str[len++] = s[i];
            str[len++] = '#';
        }
        str[len] = 0;

        // Manacher
        int mx = 0, id = 0, best = 0, pos = 0;
        for (int i = 1; i < len; ++i) {
            if (mx > i) p[i] = min(p[2*id - i], mx - i);
            else p[i] = 1;
            while (str[i - p[i]] == str[i + p[i]]) ++p[i];
            if (i + p[i] > mx) { mx = i + p[i]; id = i; }
            if (p[i] > best) { best = p[i]; pos = i; }
        }

        if (best <= 1) { puts("No solution!"); continue; }
        int L = (pos - best) / 2;
        int R = (pos + best - 2) / 2;
        printf("%d %d\n", L, R);
        for (int i = L; i <= R; ++i) putchar(s[i]);
        puts("");
    }
    return 0;
}

五、樣例驗證

Input:
b babd
a abcd

Output:
0 2
aza
No solution!

b babd：偏移 1 → c bce？實際映射後 babd → c bce 不是回文。重讀題意：給定字符代表真正的 'a'，即 ch → 'a'，其他字符按順序推導。
b 代表 a，則 c 代表 b，d 代表 c...
原串 babd：
b→a, a→z, b→a, d→c → azac 最長回文 aza（下標 0~2）。