HDU 4821 杭州現場賽：字符串哈希與滑動窗口解法詳解

HDU 4821 - String

時間限制：1000MS 記憶體限制：32768KB

問題描述

給定一個字符串 S 和兩個整數 L、M。若 S 的某個子串滿足以下條件，則稱其為「可恢復」：

1. 長度為 M × L；
2. 可由 M 個「多樣化」的子串拼接而成，每個子串長度為 L。所謂「多樣化」，指任意兩個子串在同一位置上的字符不同。

注意：從 S 不同位置截取的子串視為不同，即使內容相同。例如字符串 "aa" 有 3 個不同子串："aa"、"a"、"a"。

目標：計算 S 中不同「可恢復」子串的數量。

輸入格式

多組測試數據，直到 EOF。每組第一行包含 M 和 L，第二行是僅含小寫字母的字符串 S。|S| ≤ 10⁵，1 ≤ M·L ≤ |S|。

輸出格式

每組輸出一行，即可恢復子串的數量。

樣例

輸入：
3 3
abcabcbcaabc

輸出：
2

解題思路：滑動窗口 + 字符串哈希

本題核心在於高效判斷一個長度為 M·L 的窗口內，按長度 L 分成的 M 個塊是否兩兩「多樣化」（即任意兩塊在對應位置字符不同）。等價於這 M 個長度為 L 的子串互不相同。

採用多項式滾動哈希（基數 131，無符號長長整型自然溢出取模 2⁶⁴）對 S 做前綴哈希預處理，可 O(1) 獲取任意子串哈希值。然後枚舉起始偏移 i ∈ [0, L-1]，對以 i 為起點、步長為 L 的所有塊進行滑動窗口檢查。

具體步驟：

1. 預計算 base[k] = 131ᵏ 和前綴哈希 hash[i]。
2. 對每個偏移 i，維護一個哈希表 mm 記錄當前窗口內 M 個塊的哈希值出現次數。
3. 初始窗口：j = i, i+L, ..., i+(M-1)L，將這 M 個塊的哈希值加入 mm。若 mm.size() == M，說明互不相同，答案加一。
4. 向右滑動：每次移除最左塊，加入最右新塊，更新 mm，再判斷 mm.size()。
5. 所有偏移處理完畢即得答案。

關鍵點

• 使用 unsigned long long 自動取模 2⁶⁴，避免多模數麻煩，碰撞概率極低。
• 滑動窗口時只需 O(1) 更新哈希表，總時間複雜度 O(L × (|S|/L)) = O(|S|)。
• 注意處理字符串下標與哈希數組下標的對應（代碼中 hash[i] 為前 i 字符哈希，子串 [l, r) 哈希為 hash[r] - hash[l]*base[r-l]）。

參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 100005;
ull base[MAXN], h[MAXN];
char s[MAXN];

int main() {
    for (int i = 1; i < MAXN; ++i) base[i] = base[i-1] * 131ull;
    int M, L;
    while (scanf("%d%d", &M, &L) == 2) {
        scanf("%s", s);
        int n = strlen(s);
        h[0] = 0;
        for (int i = 1; i <= n; ++i) h[i] = h[i-1] * 131 + (s[i-1] - 'a' + 1);
        long long ans = 0;
        for (int offset = 0; offset < L && offset + M*L <= n; ++offset) {
            unordered_map<ull, int> cnt;
            for (int j = offset; j < offset + M*L; j += L) {
                ull val = h[j+L] - h[j] * base[L];
                ++cnt[val];
            }
            if (cnt.size() == M) ++ans;
            for (int j = offset + M*L; j + L <= n; j += L) {
                ull oldVal = h[j - M*L + L] - h[j - M*L] * base[L];
                if (--cnt[oldVal] == 0) cnt.erase(oldVal);
                ull newVal = h[j+L] - h[j] * base[L];
                ++cnt[newVal];
                if (cnt.size() == M) ++ans;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}