字符串哈希（HASH）

字符串哈希就是把不同的字符串映射成不同的整数，其主要的过程就是把字符串映射成一个p进制数字。

对于一个长度为n的字符串s，一般定义HASH函数为 hash(s)=i=1∑ls[i]×pl−i(modm)。

例子如下：

hash[0] = 0
hash[1] = (hash[0] * 13 + 1) % 101 = 1
hash[2] = (hash[1] * 13 + 2) % 101 = 15
hash[3] = (hash[2] * 13 + 3) % 101 = 97

如果两字符串不一样，但是HASH函数值却一样，这种情况叫做哈希碰撞

解决哈希碰撞的方法：

设置p与M的值，保证p与M互质。

M通常取大整数2的64次方，把哈希值h定义为ULL。

前缀和：一个字符串的哈希值

区间和：一个字符串字串的哈希值

求前缀和的方法就是通过上述的函数进行化值，求区间和的方法则是运用h[l，r]=h[r]-h[l-1]* $p^{r-l+1}$ 函数进行化值。

以下是一个简单的模板例题：

P3370 【模板】字符串哈希

题目描述

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

友情提醒：如果真的想好好练习哈希的话，请自觉。

输入格式

第一行包含一个整数 �N，为字符串的个数。

接下来 �N 行每行包含一个字符串，为所提供的字符串。

输出格式

输出包含一行，包含一个整数，为不同的字符串个数。

输入输出样例

输入 #1复制

5
abc
aaaa
abc
abcc
12345

输出 #1复制

说明/提示

对于 30%30% 的数据：N≤10，Mi≈6，Mmax≤15。

对于 70%70% 的数据：N≤1000，Mi≈100，Mmax≤150。

对于 100%100% 的数据：N≤10000，Mi≈1000，Mmax≤1500。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

Tip：感兴趣的话，你们可以先看一看以下三题：

BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的^_^

代码如下：

#include using namespace std;
typedef unsigned long long ULL;//定义长整型
// 定义哈希函数
ULL hash1(string s) {
    int p = 131;
    ULL hs = 0;
    for (int i = 0; i < s.size(); i++) {//从字符串的第一个字符开始依次计算，得出总的hash值
        hs = hs * p + s[i];
    }
    return hs;
}
// 定义比较函数
bool compares(int a, int b) {
    return a > b; // 修正比较函数的实现
}
int main() {
    int n, ans = 0;
    int b[10001];
    cin >> n;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        b[i] = hash1(s);
    }
    sort(b + 1, b + 1 + n, compares);//运用sort，将储存的哈希值进行排序
    for (int i = 1; i <= n; i++) {
        if (b[i] != b[i + 1]) {//排序后，如果相邻的两值不相等，则计数加一
            ans++;
        }
    }
    printf("%d", ans);//输出
    return 0;
}

分类:热门推荐日期:2024-03-28浏览:1评论:0