HDOJ 5371 Hotaru's problem：Manacher 算法求 N-序列

問題定義

N-序列：長度 3k，前 k 與後 k 相同，中間 k 與前 k 互為逆序。
即序列形式為 A + reverse(A) + A。
求最長連續子序列滿足此結構的長度。n ≤ 10⁵，答案總和 < 80 萬。

Manacher 變形

將原序列插入分隔符（如 −1），跑 Manacher 得到每個中心的最大回文半徑 p[i]。
N-序列等價於兩個相鄰回文串：A + reverse(A) 是回文，reverse(A) + A 也是回文。
枚舉中心 i，在其回文半徑內枚舉分界 j，檢查兩側是否各自為回文。

優化

只需檢查分隔符位置（對應原序列邊界），將枚舉步長設為 2。
利用 p[i] 直接判斷覆蓋關係，避免雙重循環。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int a[MAXN], b[MAXN*2], p[MAXN*2];
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int n; cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        // 建構 Manacher 序列：-2, -1, a0, -1, a1, -1, ..., -1
        int m = 0;
        b[m++] = -2; // 哨兵
        for (int i = 0; i < n; ++i) {
            b[m++] = -1; b[m++] = a[i];
        }
        b[m++] = -1; b[m++] = -3; // 結尾哨兵
        // Manacher
        int mx = 0, id = 0;
        for (int i = 1; i < m-1; ++i) {
            p[i] = mx > i ? min(p[2*id - i], mx - i) : 1;
            while (b[i + p[i]] == b[i - p[i]]) ++p[i];
            if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        }
        // 枚舉 N-序列
        int best = 0;
        for (int i = 2; i < m-2; i += 2) { // 只看分隔符位置
            for (int j = 1; j < p[i]; j += 2) { // 分界也在分隔符
                int left = i - j, right = i + j;
                // 左半段 [left, i] 需為回文 → p[left] 需覆蓋到 i
                // 右半段 [i, right] 需為回文 → p[right] 需覆蓋到 i
                if (left - p[left] + 1 <= i && right + p[right] - 1 >= i) {
                    int len = (j / 2) * 3; // 原序列長度
                    best = max(best, len);
                }
            }
        }
        cout << "Case #" << tc << ": " << best << '\n';
    }
    return 0;
}

複雜度

Manacher O(n)；枚舉中心與分界總操作數與答案總和成正比（< 80 萬），極快。