BZOJ 3916 Baltic 2014 friends：Hash + 枚舉刪除位置還原原串

題目大意

給長度為奇數的字符串 S (|S| = 2n+1)，已知 S 由某字符串 T (|T| = n) 重複兩次後，在**任意一位置**插入一個字符得到。求 T。若無解輸出 "NOT POSSIBLE"，多解輸出 "NOT UNIQUE"。

核心思路：枚舉插入位置 + Hash 判等

• 設插入位置為 `dismiss` (1-indexed)。刪除 S[dismiss] 後，剩餘 2n 字符應為 T+T。
• 分三種情況判斷前半段 == 後半段：
  1. `dismiss < mid`：插入在前半段。前半段 = S[1..dismiss-1] + S[dismiss+1..mid]，後半段 = S[mid+1..2n+1]。
  2. `dismiss == mid`：插入在中間。前半段 = S[1..mid-1]，後半段 = S[mid+1..2n+1]。
  3. `dismiss > mid`：插入在後半段。前半段 = S[1..mid-1]，後半段 = S[mid..dismiss-1] + S[dismiss+1..2n+1]。
• 用**多項式滾動 Hash** O(1) 判斷兩段是否相等。
• 收集所有合法的 T，去重（Hash 值相同視為同一解）。

關鍵代碼

#define MAX 2000010
#define BASE 23333
unsigned long long h[MAX], pw[MAX];
char s[MAX], ans[MAX];
int len, mid, cnt;
unsigned long long h_ans;

inline ull getHash(int l, int r) { return h[r] - h[l-1] * pw[r-l+1]; }

bool judge(int dismiss) {
    ull front, back;
    if (dismiss < mid) {
        front = getHash(1, dismiss-1) * pw[mid-dismiss] + getHash(dismiss+1, mid);
        back = getHash(mid+1, len);
    } else if (dismiss == mid) {
        front = getHash(1, mid-1);
        back = getHash(mid+1, len);
    } else {
        front = getHash(1, mid-1);
        back = getHash(mid, dismiss-1) * pw[len-dismiss] + getHash(dismiss+1, len);
    }
    if (front == back) {
        if (h_ans == front) return false; // 去重
        h_ans = front;
        // 提取 T (後半段)
        int top = 0;
        if (dismiss <= mid) for (int i = mid+1; i <= len; ++i) ans[++top] = s[i];
        else for (int i = 1; i < mid; ++i) ans[i] = s[i];
        return true;
    }
    return false;
}

int main() {
    cin >> len;
    if (len % 2 == 0) { puts("NOT POSSIBLE"); return 0; }
    mid = (len >> 1) + 1;
    scanf("%s", s+1);
    pw[0] = 1;
    for (int i = 1; i <= len; ++i) pw[i] = pw[i-1] * BASE;
    for (int i = 1; i <= len; ++i) h[i] = h[i-1] * BASE + s[i];
    for (int i = 1; i <= len; ++i) if (judge(i)) if (++cnt > 1) break;
    if (cnt == 0) puts("NOT POSSIBLE");
    else if (cnt == 1) puts(ans+1);
    else puts("NOT UNIQUE");
    return 0;
}

複雜度

• 預處理 Hash：O(n)。
• 枚舉 n+1 位置，每位置 O(1) Hash 判斷。總 O(n)。

關鍵點

• **Hash 判等**：O(1) 比較兩子串，避免 O(n²) 直接比較。
• **分情況構造前後段**：正確處理插入位置在前半、中間、後半三種情況的拼接。
• **去重**：用 Hash 值判斷 T 是否重複，避免多次輸出同一解。
• **邊界**：長度為偶數直接無解。

總結

BZOJ 3916 是「字符串 Hash + 枚舉刪除位置」的經典應用。核心技巧：利用 Hash 快速判斷「刪除一字符後前半等於後半」，並正確處理三種插入位置的拼接邏輯。代碼簡潔高效，O(n) 解決字符串還原問題。