您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 2084 [POI2010] Antisymmetry 反對稱子串 - Manacher 與哈希雙解

編輯：關於C++

問題定義

01 字符串中，若將 0/1 取反後再整體反轉等於原串，稱為「反對稱」。例如 00001111、010101 是反對稱，1001 不是。給定長度 N (≤ 500,000) 的 01 串，求反對稱子串個數。

性質分析

反對稱子串長度必為偶數。設子串中心在兩字符之間（偶數長度回文中心），對稱位置字符必須互為 0/1 互補。即對於中心 i，要求：

s[i-k+1] ⊕ s[i+k] = 1  (對所有 1 ≤ k ≤ len/2)

方法一：二分 + 雙向哈希

預處理正向哈希 fa（原串）和反向哈希 fb（取反後反轉串）。枚舉中心 i (1 ≤ i < n)，二分最大半徑 len，判斷 hash_a(i-len+1, i) == hash_b(i-len+1, i)。

ull hasha(int l, int r) { return fa[r] - fa[l-1]*p[r-l+1]; }
ull hashb(int l, int r) { return fb[l] - fb[r+1]*p[r-l+1]; }

// 主循環
for (int i = 1; i < n; ++i) {
    int l = 1, r = min(i, n-i), best = 0;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (hasha(i-mid+1, i) == hashb(i-mid+1, i))
            best = mid, l = mid+1;
        else r = mid-1;
    }
    ans += best;
}

時間複雜度 O(n log n)，哈希碰撞概率極低（用 64 位無符號自然溢出）。

方法二：Manacher 算法（線性時間）

構造新串：在字符間插入 #，並重新定義「匹配」規則：

# 與 # 匹配
0 與 1 匹配
1 與 0 匹配

然後直接跑標準 Manacher，統計回文半徑。每個中心貢獻 f[i] >> 1 個反對稱子串。

bool judge(char a, char b) {
    return (a=='#' && b=='#') || (a=='0' && b=='1') || (a=='1' && b=='0');
}

void manacher() {
    int mx = 0, id = 0;
    for (int i = 1; i <= n; ++i) {
        if (mx > i) f[i] = min(f[id*2-i], mx-i);
        else f[i] = 0;
        while (judge(s[i-f[i]], s[i+f[i]])) ++f[i];
        if (i+f[i] > mx) mx = i+f[i], id = i;
        ans += (f[i] >> 1);
    }
}