字符串Hash – 模板备份

O(1) 取子串Hash

O(1) 比较

通常使用 131 做乘法自然溢出即可满足要求（碰撞概率很小），如果数据不允许，可以使用两组 hash 避免哈希碰撞。也可以使用 64 位整数。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int N = 1e6;

template <typename T, size_t size, T multiplier>
struct hash_table {
    T h[size], k[size];
    hash_table() {
        k[0] = 1;
        for (int i = 1; i < size; i++) {
            k[i] = k[i - 1] * multiplier;
        }
    }
    hash_table(const char str[]) {
        new (this) hash_table();
        init(str);
    }
    void init(const char str[]) {
        memset(h, 0, sizeof(h));
        for (int i = 1; str[i]; ++i) {
            h[i] = h[i - 1] * multiplier + str[i];
        }
    }
    /** [start, end) */
    T get(size_t start, size_t end) {
        return h[end - 1] - h[start - 1] * k[end - start];
    }
};

int main() {
    char s[] = "bananananana";
    hash_table<size_t, 100, 131> ht(s);
    for (int i = 0; i < 7; i++) {
        int end = i + 2;
        printf("%d -> %d: [%.2s] %lld\n", i, end, s + i, ht.get(i, end));
    }
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.