POJ 1200 Crazy Search (Hash)：子串哈希去重完整解法

問題重述

輸入 N, NC 和文本串。統計文本中長度為 N 的不同子串數。子串總種類數 ≤ 16,000,000。樣例：3 4 daababac → 5。

哈希編碼策略

將子串視為 NC 進制數：`val = c0*NC^(N-1) + c1*NC^(N-2) + ... + c(N-1)`。
因總種類數 ≤ 1600萬，可用大數組 `hash[]` 做直接定址（Direct Addressing），O(1) 去重。

字符映射

文本字符任意 ASCII。用 `int map[256]` 將實際出現的字符映射為 1..K (K ≤ NC)。遍歷文本賦值。

完整代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXH = 16000000 + 100;
char s[MAXH];
int mapChar[256];
int hashTable[MAXH];

int main() {
    int N, NC;
    while (~scanf("%d%d", &N, &NC)) {
        getchar(); // 吃掉換行
        scanf("%s", s);
        int len = strlen(s);
        memset(mapChar, 0, sizeof(mapChar));
        memset(hashTable, 0, sizeof(hashTable));
        int charCnt = 0;
        for (int i = 0; i < len; i++) {
            unsigned char ch = s[i];
            if (!mapChar[ch]) mapChar[ch] = ++charCnt;
        }
        int ans = 0;
        for (int i = 0; i + N - 1 < len; i++) {
            long long val = 0;
            for (int j = i; j < i + N; j++) {
                val = val * NC + mapChar[(unsigned char)s[j]];
            }
            if (!hashTable[val]) {
                hashTable[val] = 1;
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

• 哈希值範圍：NC^N 可能很大，但題目保證實際不同子串數 ≤ 1600萬，數組開 16000100 安全。
• 字符映射用 `unsigned char` 避免負下標訪問越界。
• 輸入處理：`scanf("%d%d")` 後 `getchar()` 吸收換行，再 `scanf("%s")` 讀文本（無空格）。若文本含空格需用 `gets`/`fgets`。
• 時間複雜度 O(L*N)，L 為文本長度。L=10^6, N=10 時 10^7 運算，配合 O(1) 哈希可通過。

對比 map/unordered_map

直接定址數組比 `unordered_map` 快 10 倍以上，無哈希函數開銷、無動態分配，是此題 AC 關鍵。