题解：P3370 【模板】字符串哈希

· · 题解

题意

~就是字面意思。~

给定 N 个字符串，求不同字符串的个数。

哈希

哈希的本质上是把一个任意长度的序列通过哈希函数映射成尽可能不重复（又称冲突）的一个值。它也可以视为一种不可逆的压缩算法。

只要满足上述概念的算法都可叫做哈希，所以哈希有很多种，这里介绍的是进制哈希，也是相对来说较为简单的哈希：

通过选取一个 base 进制的哈希值，使得字符串转换为哈希值。这里如果 base 足够大，就不会引起冲突，所以这个哈希值是唯一的。于是我们可以通过 O(1) 的比较操作确定它们是否相等。

但是这样做在字符串过大的情况下就很容易溢出，所以还要把哈希值对一个大模数 mod 取模，即把哈希值映射到一个 0\sim mod-1 的范围中。这能解决溢出的问题但有可能造成哈希冲突。（卡模数应运而生）

冲突概率估算

首先设 Hash 的取值空间（所有可能出现的字符串的数量）为 d，计算次数（要计算的字符串数量）为 n。则 Hash 冲突的概率为：（证明见字符串哈希 - OI wiki）

p(n,d) = \frac{d!}{d^n\left(d-n\right)!} \approx 1 - \exp(-\frac{n(n-1)}{2d} )

本题 d=mod=10^{10}+1，n 取 1500，代入公式估算得

p(n,d) \approx 1 - \exp(-\frac{1500 \times 1499}{2 \times (10^{10}+1)}) \approx 0.000112425

所以只要不是出题人有意卡模数，哈希的正确性也是可观的。当然如果担心出题人卡模数，也可以用两个模数来进行双值哈希，可以大大降低冲突概率。

细节

这里字符串内包含数字、大小写字母，不好处理。所以可以直接把字符串中的字符当做整数处理。

代码

#include <bits/stdc++.h>
#define BASE 133
#define MOD 1000000007
using namespace std;
int a[11000];
int main(){
    int n;
    cin>>n;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        int x=0;
        for(int j=0;j<s.size();j++){
            x=(x*BASE+s[j])%MOD;
        }
        a[i]=x;
    }
    sort(a,a+n);
    int ans=1; // 第0项
    for(int i=1;i<n;i++){
        if(a[i]!=a[i-1])ans++;
    }
    cout<<ans;
    return 0;
}