字符串哈希

LoyalSoldier · 2025-09-26 18:33:57 · 算法·理论

字符串哈希

今天我们讲的是字符串哈希。这个名词貌似太专业了，让我们换个说法：

那么，在了解哈希之前，我们需要了解一下几个东西：

为啥需要哈希，哈希干啥的？
在我们的 c++ 中，可以用 if 语句来比较字符串的大小，时间复杂度为 O(N)。但是，当题目让我们比较多个字符串的大小的时候，如果我们每次都这样判断，可能会超时，所以我们采用一种全新的方法来快速的解决问题。

方法：将字符串 s 看成是一个 p 进制的数字，字符串的每一位代表的数字就是 s_i，在计算时采用 ASCII 码找出字符对应的数字。

关于哈希的三个专业名词：

双射：假设没有哈希这坨东西，但是我想要将一个字符串转换成一个数字，如果我想将字符 c 替换成数字 x。这种情况就是双射。（对于所有的 x 都要满足该条件，且所有的数字要用光）简单说：字符串和数字一一对应，并且不用的字符串得到的数字不一样，数字会全部用光的情况叫做双射。

单射：每一个字符对应唯一一个数字。比如字符 'A' 对应 6，那么字符 A 将不再对应其他数字。

满射：每一个字符都对应一个数字而且数字全部用光。需要注意：同一个数字可以表示多种字符，这里不再多阐述。

哈希如何实现。

单模数哈希：那么在这里，我们采用 p 进制来处理。具体来说，我们把这个字符串转换成一个 p 进制的数字。比如字符串 S，那么转换后的数字就是 S_{len} \times p^0+S_{len-1} \times p^1 + ... +S_0 \times p^{len}在这里，我们的 p 不能太小。因为在这里，会哈希冲突。原因很简单，有可能不同字符串转换成的数字不一样，因此将单个数位的权值扩大，冲突概率越小。

注意：数字可能很大，考虑 unsigned long long 可以自动取模，所以在这里我们考虑 #define int unsigned long long。

实现：

const int p=131;//也可以是13331，随便你。
int get_hash(string s){
    int tmp=0;
    for(int i=0;i<s.size();i++){
        tmp=tmp*p+s[i];
    }
    return tmp;
}

双模数哈希：

我们刚刚说了单模数哈希可能会有哈希冲突，那么有若干名 Oier 可能会想：如果我们用取模两个数字呢？的确可以这样，但是这样很可能会出错（代码没问题但是实现容易错）。比如你看这个字符串是否出过时需要有标记数组，但是如果两个哈希值都出现过才代表出现。即 vis_{hash1}=1,vis_{hash2}=1 才可以。如果你是 vis_{hash1}=0,vis_{hash2}=0 那就错了。因为你如果两个哈希值有一个出现了但是另外一个没有出现过证明该字符串也没有出现过的，毕竟这是双模数哈希，需要看的是两个哈希值。本方法复杂，不建议使用。

万能哈希：工程开发哈希。

那么既然会哈希冲突，肯定有保险的方法。因为考虑余数会哈希冲突，所以我们需要开一个 vector 的二维数组。定义状态：v_{i,s} 表示当哈希值为 i 时有字符串 s 的哈希值为 i。如果需要判断 s 是否需要装进数组，就可以扫一遍数组看 s 是否有了。这样就可以避免我们的哈希冲突。可能有警钟：每次都要扫一遍数组，小心数据范围，太大可能会超时。

实现：

    int hash=0;
    for(int i=0;i<s.size();i++){
        hash=(hash*130+s[i])%mod;
    }
    for(int i=0;i<b[hash].size();i++){
        if(b[hash][i]==s){
            return ;
        }
    }
    b[hash].push_back(s);

手都废了。。。。。。。

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

如题，给定 N 个字符串（第 i 个字符串长度为 M_i，字符串内包含数字、大小写字母，大小写敏感），请求出 N 个字符串中共有多少个不同的字符串。

这简单啊，对于每一个 s_i，求出它的哈希值，如果这个哈希值出现过，跳过，否则答案多一，最后输出啊。

在这里我了补充一下双哈希，在这里我采用双哈希。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn=1e7+5;
bool tong[maxn];
const int p=131;
const int pp=13331;
int get_hash(string s){
    int tmp=0;
    for(int i=0;i<s.size();i++){
        tmp=tmp*p+s[i];
    }
    return tmp%maxn;
}
int get_hash2(string s){
    int tmp=0;
    for(int i=0;i<s.size();i++){
        tmp=tmp*pp+s[i];
    }
    return tmp%maxn;
}
signed main(){
    int t;
    cin>>t;
    int cnt=0;
    while(t--){
        string s;
        cin>>s;
        int ans=get_hash(s);
        int ans2=get_hash2(s);
        if(tong[ans]==1&&tong[ans2]==1) continue;
        cnt++;
        tong[ans]=1; 
        tong[ans2]=1;
    }
    cout<<cnt;
    return 0;
}

P10468 兔子与兔子

本题考察算法：子串哈希。

第一行输入一个 DNA 字符串 S。

第二行一个数字 m，表示 m 次询问。

接下来 m 行，每行四个数字 l_1, r_1, l_2, r_2，分别表示此次询问的两个区间，注意字符串的位置从 1 开始编号。问，这两个字符串是否相同。

本题可以考虑暴力。对于每次询问，把两个字符串进行相加。时间复杂度 O(N \times M)。超时。
考虑哈希。对于我们的这个哈希，我们定义状态为 hs_i 为字符串中前 i 个字符所组成的字符串的哈希值。那么在这里，我们的转移过程为：hs_i=hs_{i-1} \times p + s_i。即：把前面的字符串向左边移动一位，新的一位留给 s_i。新的字符串=原来的+s[i]。因为题目比的是一个区间，那么我们可以把这个哈希值用前缀和快速求出。如果求区间 [l,r]。那么公式如下： [l,r]=sum[r]-sum[l-1] \times pw[r-l+1]
解析：当要保留 [l,r] 时，需要删除的是前 l-1 个字符。我们普通的求值方法是 sum[r]-sum[l-1]。但是在这里，我们是转进制，有权值变化。第 i 为的权值为 i \times (len-i)。len-i 表示后要乘 i 次 p。根据我们的哈希转移来的。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn=1e7+5; 
const int p=131;
int sum[maxn],pw[maxn];
int tong[maxn];
string s;
int m;
int get_hash(int l,int r){
    return sum[r]-sum[l-1]*pw[r-l+1];
}
signed main(){
    cin>>s;
    int len=s.size();
    s=" "+s;
    pw[0]=1;
    for(int i=1;i<=len;i++){
        sum[i]=sum[i-1]*p+s[i];
        pw[i]=p*pw[i-1];
    }
    cin>>m;
    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get_hash(l1,r1)==get_hash(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

CF39J Spelling Check

Petya 发现，当他用键盘打字时，他经常多打出一个字母。他想要发明一个自动改正单词的程序，能够将他打出的单词删去一个字母，改为字典中对应的正确单词。请你帮助他写一个程序，从打出的单词中删去哪一个字母，才能改为字典中的那个单词？

和上一题几乎一样，考虑枚举被删除的字符位置。那么我们的区间就是 [i,i]。计算标准哈希值与删去字符后的哈希值是否相同即可。代码在这里不再展示，很简单。

以上就是字符串哈希的基础部分，希望能帮助到大家。后期会考虑更新的。如果对大家有帮助，麻烦给一个小小的赞！