【基础算法】字符串哈希

简介: 【基础算法】字符串哈希
🌹作者:云小逸
📝个人主页: 云小逸的主页
📝Github: 云小逸的Github
🤟motto:要敢于一个人默默的面对自己, ==强大自己才是核心==。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏👏专栏:Linux学习👏
👏专栏:C语言初阶👏👏专栏:数据结构👏👏专栏:备战蓝桥杯👏

@TOC


前言

今天这篇文章讲解的是哈希的另一种题型:字符串前缀哈希法,希望我的讲解你可以喜欢,谢谢。
——————————————————————————————

首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.把时间分给睡眠,分给书籍,分给运动,分给花鸟树木和山川湖海,分给你对这个世界的热爱,而不是将自已浪费在无聊的人和事上。当你开始做时间的主人,你会感受到平淡生活中喷涌而出的平静的力量,至于那些焦虑与不安,自然烟消云散。

2.毕淑敏说过:在光芒万丈之前,我们都要欣然接受眼下的难堪和不易,接受一个人的孤独和偶尔的无助,认真做好眼前的每件事,你想要的都会有。你要知道,所有的逆袭都是有备而来。
所以,请你一定要站在自己所热爱的世界里,闪闪发光。这归途尚远,要迷人,且倔强。

3.人生的际遇,不是等来的,而是拼出来的。是自律的汗水,也是前行的坚韧。当你付出了足够的努力、积攒了足够的实力,自会拨开人生的迷雾,收获属于自己的精彩。

4.有段话讲得很好:刷一宿视频是我的人性,但刷完视频后的空虚感和对浪费时间的悔恨也是我的人性。胡吃海喝是我的人性,但身材走形看着镜子里发胖的自己,心里难受也是我的人性。所谓延迟满足,重点不在延迟,而在于满足。压抑当下的小人性,是为了成就未来的大格局。自律的人,只不过比放纵的人看得远了一点而己。

5.自律不是表演给自己或者其他人看的,它需要强大的内心动力,紧盯着未来那个宏大的目标,眼下这点小约束就会变得微不足道。生活里真正的强者,是即使怀揣着痛苦和悲伤,也能热爱生活的人,也是靠着某个信念抵挡住外界的诱惑,仍旧努力做好每件事的人。

字符串前缀哈希法:

核心思想:

字符串前缀哈希法是一种比较特殊的哈希方法,它是先预处理出所有字符串前缀的哈希,利用哈希数组进行存储,下标是0开始的,h[0]是等于0的。
例如:
字符串“abcabcde”
h[0]=0;
h[1]="a"的hash(哈希)值;
h[2]="ab"的hash值;
h[3]="abc"的hash值;
……

如何定义某一个前缀的哈希值?(将字符串转换为数字)

将字符串看成P进制的数,然后将P进制的数转换为十进制的数字:
在这里插入图片描述
这样转换成十进制的数字,可能非常大,因为字符串可能有10到20个,这转换后就是很大很大的数字,容易溢出和出现错误,因此可以对Q进行取模,使其映射到【0,Q-1】;

1.不可以映射成0:

如:
a----------0;
aa--------00,
这样就不对了,两个不同的字符串映射成一样的结果,造成冲突

2.会存在冲突:

将P和Q设定的非常好,就可以极大概率避免冲突(99.999%):
P=131or13331
Q=2^64^;
这里取Q=2^64^,这里可以直接定义哈希数组为unsigned long long ,它会使超过2^64^的数溢出,溢出的值就等价于对2^64^取模。

好处:利用前面算的前缀哈希可以求出任意一段的子串的哈希值。

在这里插入图片描述
如图上面的这个图:
我们已知:h[R]和h[L-1]的哈希值,怎么求出L到R的哈希值?
在这里插入图片描述
上面我们不是假设了字符串为以P为进制的数字,则右边是高位,左边是低位,
h[i]=h[i−1]×P+hash(s[i]);
故hash(s[l..r])=h[r]−h[l−1]×Pr−l+1;

例题:

题目:

给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1]
和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m,表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。

接下来 m 行,每行包含四个整数 l1,r1,l2,r2,表示一次询问所涉及的两个区间。

注意,字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例:

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例:

Yes
No
Yes

代码:

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;//将P和Q设定的非常好,就可以极大概率避免冲突(99.999%):
                               //P=131or13331
const int N = 100010, P = 131; //Q=2^64^;
                               //这里取Q=2^64^,这里可以直接定义哈希数组为unsigned long long ,
                               //它会使超过2^64^的数溢出,溢出的值就等价于对2^64^取模。
int n, m;
char str[N];
ULL h[N], p[N];//p[N]是存放要乘以p的多次方

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);//因为如果直接用 scanf("%s",str); 的话,就会出现一个问题:
                         //scanf函数遇到空格或TAB,就会停下来。所以用指针的方式就可以防止这种情况发生。
                        //输入str第一个元素之后的字符串,给str[1]赋值
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

代码解析:

1.解决冲突:

typedef unsigned long long ULL;//将P和Q设定的非常好,就可以极大概率避免冲突(99.999%):
                               //P=131or13331
const int N = 100010, P = 131; //Q=2^64^;
                               //这里取Q=2^64^,这里可以直接定义哈希数组为unsigned long long ,
                               //它会使超过2^64^的数溢出,溢出的值就等价于对2^64^取模。
int n, m;
char str[N];
ULL h[N], p[N];//p[N]是存放要乘以p的多次方

2.scanf("%s", str + 1);

 scanf("%s", str + 1);//因为如果直接用 scanf("%s",str); 的话,就会出现一个问题:
                         //scanf函数遇到空格或TAB,就会停下来。所以用指针的方式就可以防止这种情况发生。
                        //输入str第一个元素之后的字符串,给str[1]赋值

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:

1.莫言在《晚熟的人》当中说:真正的强大不是忘记,而是接受接受分道扬镳,接受世事无常,接受孤独挫败,接受突如其来的无力感,接受自己的不完美,接受困惑、不安、焦虑和遗憾,调整自己的状态,找到继续前行的力量,成为更好的自己。是的,与其苦苦的想忘记,不如坦然接受。

2.接受你最闪耀的时候,不骄傲;接受你最糟糕的时候,不气馁;接受你最平淡无奇的时候,不放弃。正如王朔对女儿说的:内心强大到混蛋,比什么都重要。

3.三毛曾说过:“给自己时间,不要焦急,一步一步来,一日一日过,请相信生命的韧性是惊人的,跟自己的心去合作,不要放弃对自己的爱护。

4.当你的能力还驾驭不了你的目标时,你就应该沉下心来历练。祛除杂念,不好高骛远,也不轻言放弃。信手拈来的从容都是厚积薄发的沉淀,找到一个准确的定位,认真打磨自己,慢慢就能变得波澜不惊,在喧嚣中宁静致远。但愿你心安,向内探求不停,做有心的蓄积者,沉淀自己,升华自己。

5.有心栽花花不开,无心插柳柳成荫。生活有时候很有意思,你越是用力证明,越感觉疲惫。越是对一件事的结果产生执念,就越反着来。太过用力,本身就是一种消耗,反而适得其反,用温柔的力量,反而能厚积薄发,就像发条上的太紧容易断,该放松时放松,该努力时努力,张弛有度才刚刚好。不骄不躁,抚平心态,才能看到更好的阳光。不要一味地追求太紧绷的用力,人生最坏的结果不过是大器晚成。

最后如果觉得我写的还不错,请不要忘记==点赞==✌,==收藏==✌,加==关注==✌哦(。・ω・。)

愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油,为自己点赞!

目录
相关文章
|
28天前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
1月前
|
算法 安全 JavaScript
安全哈希算法:SHA算法
安全哈希算法:SHA算法
28 1
安全哈希算法:SHA算法
|
26天前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
1月前
|
JavaScript 算法 前端开发
国标哈希算法基础:SHA1、SHA256、SHA512、MD5 和 HMAC,Python和JS实现、加盐、算法魔改
国标哈希算法基础:SHA1、SHA256、SHA512、MD5 和 HMAC,Python和JS实现、加盐、算法魔改
159 1
|
2月前
|
缓存 负载均衡 算法
(四)网络编程之请求分发篇:负载均衡静态调度算法、平滑轮询加权、一致性哈希、最小活跃数算法实践!
先如今所有的技术栈中,只要一谈关于高可用、高并发处理相关的实现,必然会牵扯到集群这个话题,也就是部署多台服务器共同对外提供服务,从而做到提升系统吞吐量,优化系统的整体性能以及稳定性等目的。
|
2月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
228 1
|
2月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
1月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
44 0
|
3月前
|
存储 算法 安全
深入理解SHA系列哈希算法:安全性的保障与演进
深入理解SHA系列哈希算法:安全性的保障与演进
|
3月前
|
存储 算法 Java
Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。
【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
33 1