POJ 1200 Crazy Search：哈希統計固定長度不同子串數量

題目大意

給定子串長度 N、字符集大小 NC、文本串，求文本中長度為 N 的不同子串個數。子串總數不超過 1600 萬。

算法：基於字符集的哈希編碼

1. 將文本中出現的字符映射為 1..NC 的整數。
2. 將長度 N 的子串視為 NC 進制數，計算哈希值 hash = Σ c[i] * NC^(N-1-i)。
3. 用大數組 ha[16000005] 直接定址標記（位圖），ha[hash]=1 表示出現過。
4. 掃描所有子串，統計未重複的哈希值個數。

關鍵代碼

#include <cstdio>
#include <cstring>
#define N 16000005
char a[N]; int ha[N];
int main() {
    int n, m; // n=子串長度, m=字符集大小
    while (~scanf("%d%d", &n, &m)) {
        scanf("%s", a);
        int len = strlen(a);
        // 字符映射
        int map[256] = {0}, cnt = 0;
        for (int i=0; i

複雜度與優化

時間：O(L * N)，L 為文本長度。可用滾動哈希優化至 O(L)，但題目數據範圍直接雙層循環即可通過。
空間：16M * 4 bytes ≈ 64MB，符合限制。
輸入巨大，必須用 scanf。