网站兼容性,百度的首页,wordpress交友模板,邀请注册推广赚钱的app#x1f339;作者:云小逸 #x1f4dd;个人主页:云小逸的主页 #x1f4dd;Github:云小逸的Github #x1f91f;motto:要敢于一个人默默的面对自己#xff0c;强大自己才是核心。不要等到什么都没有了#xff0c;才下定决心去做。种一颗树#xff0c;最好的时间是十年前… 作者:云小逸 个人主页:云小逸的主页 Github:云小逸的Github motto:要敢于一个人默默的面对自己强大自己才是核心。不要等到什么都没有了才下定决心去做。种一颗树最好的时间是十年前其次就是现在学会自己和解与过去和解努力爱自己。希望春天来之前我们一起面朝大海春暖花开 专栏C 专栏Java语言专栏Linux学习 专栏C语言初阶专栏数据结构专栏备战蓝桥杯 文章目录前言字符串前缀哈希法核心思想如何定义某一个前缀的哈希值将字符串转换为数字1.不可以映射成02.会存在冲突好处利用前面算的前缀哈希可以求出任意一段的子串的哈希值。例题题目输入格式输出格式数据范围输入样例输出样例代码代码解析最后前言
今天这篇文章讲解的是哈希的另一种题型字符串前缀哈希法希望我的讲解你可以喜欢谢谢。 ——————————————————————————————
首先先写上几句话献给坚持创作的我和点开这篇文章希望进步的你 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进行取模使其映射到【0Q-1】
1.不可以映射成0
如 a----------0 aa--------00 这样就不对了两个不同的字符串映射成一样的结果造成冲突
2.会存在冲突
将P和Q设定的非常好就可以极大概率避免冲突99.999% P131or13331 Q264; 这里取Q264,这里可以直接定义哈希数组为unsigned long long 它会使超过264的数溢出溢出的值就等价于对264取模。
好处利用前面算的前缀哈希可以求出任意一段的子串的哈希值。 如图上面的这个图 我们已知:h[R]和h[L-1]的哈希值怎么求出L到R的哈希值 上面我们不是假设了字符串为以P为进制的数字则右边是高位左边是低位 h[i]h[i−1]×Phash(s[i]) 故hash(s[l…r])h[r]−h[l−1]×Pr−l1;
例题
题目
给定一个长度为 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 algorithmusing namespace std;typedef unsigned long long ULL;//将P和Q设定的非常好就可以极大概率避免冲突99.999%//P131or13331
const int N 100010, P 131; //Q2^64^;//这里取Q2^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%//P131or13331
const int N 100010, P 131; //Q2^64^;//这里取Q2^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.有心栽花花不开无心插柳柳成荫。生活有时候很有意思你越是用力证明越感觉疲惫。越是对一件事的结果产生执念就越反着来。太过用力本身就是一种消耗反而适得其反用温柔的力量反而能厚积薄发就像发条上的太紧容易断该放松时放松该努力时努力张弛有度才刚刚好。不骄不躁抚平心态才能看到更好的阳光。不要一味地追求太紧绷的用力人生最坏的结果不过是大器晚成。
最后如果觉得我写的还不错请不要忘记点赞✌收藏✌加关注✌哦(ω)
愿我们一起加油奔向更美好的未来愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油为自己点赞
