字符串哈希

目录

一、例题acwing841. 字符串哈希 -前缀哈希

二、例题洛谷P3370 字符串哈希-set哈希

三、其他哈希题-力扣网站

字符串哈希是一种高效的字符串比较与查找方法，它通过将字符串映射为数字，使得两个字符串相等当且仅当其哈希值相等。

字符串一一映射为数字，两个数字相等完全等价于字符串相等。

【C++算法模板】字符串哈希，超详细注释带例题_字符串哈希模板-CSDN博客  ----推荐学习博客

一、例题acwing841. 字符串哈希 -前缀哈希

yxc版
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
    
    
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

#include<bits/stdc++.h>
using namespace std;

// 定义无符号长整型别名UL
typedef unsigned long long ULL;
// 定义常量N表示字符串的最大长度，P为哈希计算时的底数
const int N = 100010, P = 131;
// 数组h用于保存从字符串起始位置到第i个字符的哈希值（即前缀哈希值），这样可以方便地通过已有的前缀哈希值来计算任意子字符串的哈希值
ULL h[N];
// 数组p用于保存P的i次幂，在计算哈希值过程中会用到
ULL p[N];
char str[N];

// 函数get用于计算子串从位置l到位置r的哈希值
// 通过利用前缀哈希值h以及P的幂次p来快速计算出指定子串的哈希值
ULL get(int l, int r)
{
  
    // 具体计算方式是用位置r的前缀哈希值h[r]减去位置l - 1的前缀哈希值h[l - 1]乘以P的(r - l + 1)次幂
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    int n, m;
    // 读取输入的字符串长度n和询问次数m，同时将输入的字符串存储到str数组中，从str[1]开始存储
    scanf("%d %d%s", &n, &m, str + 1);
    // 初始化p[0]为1，因为任何数的0次幂都为1，这是后续计算P的幂次的基础
    p[0] = 1;
    // 循环计算P的幂次p[i]以及字符串的前缀哈希值h[i]
    for (int i = 1; i <= n; i++)
    {
        // 计算P的i次幂，即p[i]等于p[i - 1]乘以P
        p[i] = p[i - 1] * P;
        // 计算从字符串起始位置到第i个字符的前缀哈希值h[i]
        // 计算方式是用上一个位置的前缀哈希值h[i - 1]乘以P再加上当前字符str[i]的ASCII码值
        h[i] = h[i - 1] * P + str[i];
    }

    
    while (m--)
    {
        int l1, r1, l2, r2;
  
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2))
            puts("Yes");
   
        else
            puts("No");
    }
    return 0;
}

二、例题洛谷P3370 字符串哈希-set哈希

#include<iostream>
#include<set>
using namespace std;
 
set<string> se;
 
int main()
{
    string s;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	cin>>s;
    	se.insert(p);
	}
	cout<<se.size();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int P = 131, N = 10010;
typedef unsigned long long ULL;
string str;
ULL h[N], p[N];

int main() {
    int n;
    cin >> n;
    p[0] = 1;

    // 使用集合来存储已经出现过的哈希值
    set<ULL> hashSet;

    for (int i = 1; i <= n; i++) {
        cin>>str;
        int len = str.size();
        for (int j = 1; j <= len; j++) {
                p[j] = p[j - 1] * P;
                h[j] = h[j - 1] * P + str[j ];
        }

        // 将当前字符串的完整哈希值加入集合
        hashSet.insert(h[len]);

    }

    // 集合中元素的个数就是不同字符串的数量
    cout << hashSet.size();

    return 0;
}

三、其他哈希题-力扣网站