当前位置: 首页 > article >正文

字符串哈希

目录

一、例题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;
}

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

1790. 仅执行一次字符串交换能否使两个字符串相等 - 力扣(LeetCode)双指针算法 简单
976. 三角形的最大周长 - 力扣(LeetCode)排序+简单贪心 简单
1207. 独一无二的出现次数 - 力扣(LeetCode)哈希map统计次数+set查次数是否唯一 简单
234. 回文链表 - 力扣(LeetCode)双指针算法 简单
1. 两数之和 - 力扣(LeetCode)hash map 较简单
1920. 基于排列构建数组 - 力扣(LeetCode)简单的不能再简单
15. 三数之和 - 力扣(LeetCode)双指针算法 中等。。。其实也不难

http://www.kler.cn/a/585799.html

相关文章:

  • 【硬件测试】基于FPGA的16PSK+帧同步系统开发与硬件片内测试,包含高斯信道,误码统计,可设置SNR
  • 数学建模之数学模型-3:动态规划
  • C# 集合
  • 卷积神经网络(CNN)之 EfficientNet
  • 【RTSP】客户端(三) 音频相关
  • 计算机视觉算法实战——花卉识别(主页有源码)
  • Spring框架详解(IOC容器-上)
  • JVM 如何保证 Java 程序的安全性?
  • TypeScript 高级类型 vs JavaScript:用“杂交水稻”理解类型编程
  • 【redis】set 类型:基本命令
  • 遥感数据获取、处理、分析到模型搭建全流程学习!DeepSeek、Python、OpenCV驱动空天地遥感数据分析
  • WPF程序使用AutoUpdate实现自动更新
  • Secs/Gem第一讲(基于secs4net项目的ChatGpt介绍)
  • 完善机器人:让 DeepSeek 使用Vue Element UI快速搭建 AI 交互页面
  • 【Linux系统编程】管道
  • 什么是mysql索引回表?
  • 杨辉三角形(信息学奥赛一本通-2043)
  • 智慧应急消防解决方案(35页PPT)(文末有下载方式)
  • doris:SQL 方言兼容
  • 【0x80070666】-已安装另一个版本...(Tableau 安装失败)