HDU 3973 字符串哈希 + 線段樹：動態子串存在性查詢

題目大意

給定字典 {W_i}，長字符串 S（|S|≤1e5）。支持兩操作：
Q L R：查詢 S[L..R] 是否在字典中。
C X Y：將 S[X] 改為字符 Y。
多測試用例，字典總長 ≤ 2e6，操作數 ≤ 1e5。

解法：線段樹維護多項式哈希

字符串哈希：`H[i] = H[i-1]*seed + (s[i]-'a'+1)`，`seed=31`，用 `unsigned long long` 自然溢出模 2^64。
線段樹節點存儲區間哈希值，合併：`hash = left.hash * pow[right.len] + right.hash`。
單點更新 O(log n)，區間查詢哈希 O(log n)。

字典預處理

讀入所有字典詞，計算其哈希值存入 `unordered_set`（或 `set`），查詢時計算子串哈希 O(1) 判斷是否存在。

關鍵代碼結構

struct Node { int l,r; ULL hash; } tree[4*MAXN];
ULL powBase[MAXN]; // seed^i

void build(int l,int r,int rt) { ... }
void update(int pos,char val,int rt) { ... }
ULL query(int L,int R,int rt) { ... }

複雜度

預處理字典 O(總長)。每操作 O(log |S|)，總 O((|S|+Q) log |S|)，極易通過。

注意點

• 哈希碰撞概率極低，可雙哈希（兩個 seed/mod）進一步保險。
• 線段樹下標 0-based/1-based 統一。
• 輸出格式 `Case #idx:`。

總結

經典「字符串哈希 + 線段樹」模板題，將動態子串哈希查詢轉化為區間哈希合併，配合字典哈希集合 O(1) 判斷，代碼結構清晰，是字符串動態問題必會技巧。