字符串哈希

O_Yeee · 2025-11-15 16:28:45 · 个人记录

(csp-sT3字符串没有一点头绪，看来是字符串题写少了，还是一点点学吧)

字符串哈希

注意到哈希的原理就是这个样子的

进制哈希。进制哈希的核心便是给出一个固定进制 base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个 base 进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同。

很显然，这个样子极有可能会发生哈希冲突，此时需要降低产生冲突的几率。有两种方法：

• 记录一下每个字符串所对应的哈希值，此时如果有一个值与之前的相同，这时你就随意加上一个大数，直到不在冲突。
• 用多种哈希方式来解析一个字符串，然后比对每一种哈希值，此时就能得到较为正确的解。

这两种方式各有利弊，第一种虽然不会有错误，但是因为数字比较大会导致空间超限，而第二种对空间的要求就稍微小一点，但是相应的存在字符串可以被卡掉，但是一般还是用后面的，因为MLE还是更容易一点

这里给出 P3370 单哈希代码

#include <bits/stdc++.h>
using namespace std;
string s;int a[10005];
const int Mod = 998244353, base = 20;
void Hash(string s, int id){
    int n = s.size();
    s = ' ' + s;
    for(int i = 1; i <= n; i++){
        a[id] = (s[i] - 48) + a[id] * base;
        a[id] %= Mod;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s;
        Hash(s, i);
    }
    sort(a + 1, a + n + 1);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(a[i] != a[i - 1])ans++;
    cout << ans;
    return 0;
}

大概就是酱紫的，所以其实不是特别难。（为什么没在csp之前学啊）