您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1200 Crazy Search：字串哈希求不同子串個數（滾動哈希）

編輯：關於C++

POJ 1200 Crazy Search 完整解析

給定子串長度 N、字元集大小 NC、母串。求母串中長度為 N 的不同子串個數。子串總數 ≤ 1600 萬，適用哈希表去重。

核心算法：基數編碼 + 滾動哈希

將字元映射為 0~NC-1，子串視為 NC 進制數：

hash = c₀×NCⁿ⁻¹ + c₁×NCⁿ⁻² + ... + cₙ₋₁

滾動更新：

hash = (hash - c₀×NCⁿ⁻¹) × NC + cₙ

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MAXH = 16000010;
bool hash_table[MAXH];
int char_map[256];
char str[1000100];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, base;
    while (cin >> N >> base) {
        cin >> str;
        int len = strlen(str);
        
        // 字元映射
        memset(char_map, 0, sizeof(char_map));
        int mapped = 0;
        for (int i = 0; i < len; i++) {
            if (!char_map[(int)str[i]]) char_map[(int)str[i]] = ++mapped;
            if (mapped == base) break;
        }
        
        // 初始哈希
        long long hash = 0, pow = 1;
        for (int i = 0; i < N; i++) {
            hash = hash * base + char_map[(int)str[i]] - 1;
            if (i < N - 1) pow *= base;
        }
        
        memset(hash_table, 0, sizeof(hash_table));
        hash_table[hash] = true;
        int ans = 1;
        
        // 滾動
        for (int i = 1; i <= len - N; i++) {
            hash = (hash - (char_map[(int)str[i-1]] - 1) * pow) * base + char_map[(int)str[i+N-1]] - 1;
            if (!hash_table[hash]) {
                hash_table[hash] = true;
                ans++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}