哈希冲突

1 哈希冲突

如果使用普通哈希解决问题，可能会发生哈希值重复的情况，这就是哈希冲突。

假设每道题的数据都是随机的。

设模数为 $M$，比较次数为 $N$，一次比较错误率为 $\frac{1}{M}$，总错误率为
$$1-{\left(1-\frac{1}{M}\right)}^N$$
当 $M=10^9,N=10^7$ 时，这个式子的结果大约为 $1\%$。

考虑到大多数题目有 $20$ 组数据，因此一道题目的总错误率为 $20\%$。

而且，大多数题目会制定一些特殊数据，所以，这个值可能会更高。

因此，为了解决这个问题，使用双哈希，即使用两套模数和底数来计算哈希值，双重保险。

注：常见的底数有 $128,131,26,31$ 等；常见的模数有 $10^9+7,998844353$ 等。

2 哈希模板

typedef long long ll;
struct HASH {
    ll sed, mod, h[N], pw[N];
    void init(ll ser_in, ll mod_in) {  //初始化
        sed = ser_in, mod = mod_in;
        pw[0] = 1;
        for (int i = 1; i < N; i++)
            pw[i] = pw[i - 1] * sed % mod;
    }
    void make(string s) {  //计算哈希值
        h[1] = s[1] % mod;
        for (int i = 2; i <= n; i++)
            h[i] = (h[i - 1] * sed % mod + s[i]) % mod;
    }
    ll get(int l, int r) {  //获取子串哈希值
        return (h[r] - h[l - 1] * pw[r - l + 1] % mod + mod) % mod;
    }
};

3 例题

3.1 不同子串

题目描述

给定一个长度为 $n$ 的字符串 $S$，问 $S$ 中有多少个长度为 $L$ 的不同的子串。

题解

双哈希，使用 $(131,10^9+7)$ 和 $(128,998244353)$ 两套哈希。

利用 set 去重的特性，把两种哈希值作为一个 pair 存入 set，去重后个数即为所求。

int main() {
    CLOSE;
    cin >> n >> L;
    cin >> s;
    s = " " + s;
    HASH S1, S2;
    S1.init(131, 1e9 + 7), S2.init(128, 998244353);
    S1.make(s), S2.make(s);
    set<pair<ll, int>> p;
    int ans = 0;
    for (int i = 1; i <= n - L + 1; i++)
        p.insert(make_pair(S1.get(i, i + L - 1), S2.get(i, i + L - 1)));
    cout << p.size();
    return 0;
}

3.2 [POI2012] OKR-A Horrible Poem

P3538 [POI2012] OKR-A Horrible Poem - 洛谷

题目描述

给出一个由小写英文字母组成的字符串 $S$，再给出 $q$ 个询问，要求回答 $S$ 某个子串的最短循环节。

如果字符串 $B$ 是字符串 $A$ 的循环节，那么 $A$ 可以由 $B$ 重复若干次得到。

题解

如果 $T$ 是 $S$ 的循环节，则 $|T|$ 是 $|S|$ 的因子。

而判断一个串的循环节，要按照它的因子从大到小判断。为了使字符串的下一个子串的长度尽可能长，所以前者的长度一定要除以一个最小的不为 $1$ 的因子，得到后者的长度。

可以发现，每个数字的最小的不为 $1$ 的因子是其最小的质因子。

而欧拉筛的性质就是尽可能用最小的质因子筛掉数字。

ll prime[N], g[N], size = 0;
bool is_prime[N];
void Euler_prime(int n) {
    is_prime[0] = is_prime[1] = true;
    size = 0;
    g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) prime[++size] = i, g[i] = i;
        for (int j = 1; j <= size && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = true;
            g[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}
//some code...
int main() {
    CLOSE;
    //some code...
    while (q--) {
        cin >> l >> r;
        ll ans = r - l + 1, len = r - l + 1;
        if (t.get(l + 1, r) == t.get(l, r - 1)) { //特判：循环节为1的情况
            cout << 1 << endl;
            continue;
        }
        while (len > 1) {
            // 每次让长度除以质因子，得到一个新的长度
            if (t.get(l + ans / g[len], r) == t.get(l, r - ans / g[len])) {
                ans /= g[len];
            }
            len /= g[len]; //缩小长度
        }
        cout << ans << endl;
    }
    return 0;
}