专栏文章

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

hhcx2012
P3370题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipoyq6y
此快照首次捕获于
2025/12/03 15:34
3 个月前
此快照最后确认于
2025/12/03 15:34
3 个月前
查看原文

题意

~就是字面意思。~
给定 NN 个字符串，求不同字符串的个数。

哈希

哈希的本质上是把一个任意长度的序列通过哈希函数映射成尽可能不重复（又称冲突）的一个值。它也可以视为一种不可逆的压缩算法。
只要满足上述概念的算法都可叫做哈希，所以哈希有很多种，这里介绍的是进制哈希，也是相对来说较为简单的哈希：
通过选取一个 basebase 进制的哈希值，使得字符串转换为哈希值。这里如果 basebase 足够大，就不会引起冲突，所以这个哈希值是唯一的。于是我们可以通过 O(1)O(1) 的比较操作确定它们是否相等。
但是这样做在字符串过大的情况下就很容易溢出，所以还要把哈希值对一个大模数 modmod 取模，即把哈希值映射到一个 0∼mod−10\sim mod-1 的范围中。这能解决溢出的问题但有可能造成哈希冲突。（卡模数应运而生）

冲突概率估算

首先设 Hash 的取值空间（所有可能出现的字符串的数量）为 dd，计算次数（要计算的字符串数量）为 nn。则 Hash 冲突的概率为：（证明见字符串哈希 - OI wiki）
p(n,d)=d!dn(d−n)!≈1−exp⁡(−n(n−1)2d)p(n,d) = \frac{d!}{d^n\left(d-n\right)!} \approx 1 - \exp(-\frac{n(n-1)}{2d} )
本题 d=mod=1010+1d=mod=10^{10}+1，nn 取 15001500，代入公式估算得
p(n,d)≈1−exp⁡(−1500×14992×(1010+1))≈0.000112425p(n,d) \approx 1 - \exp(-\frac{1500 \times 1499}{2 \times (10^{10}+1)}) \approx 0.000112425
所以只要不是出题人有意卡模数，哈希的正确性也是可观的。当然如果担心出题人卡模数，也可以用两个模数来进行双值哈希，可以大大降低冲突概率。

细节

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

代码

CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...