个人主页:云小逸的主页
:云小逸的
motto:要敢于一个人默默的面对自己，强大自己才是核心 。不要等到什么都没有了，才下定决心去做 。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己 。==希望春天来之前，我们一起面朝大海，春暖花开！==
专栏：C++ 专栏：Java语言专栏：Linux学习
专栏：C语言初阶专栏：数据结构专栏：备战蓝桥杯
文章目录字符串前缀哈希法：好处：利用前面算的前缀哈希可以求出任意一段的子串的哈希值 。例题： 代码：代码解析：? 最后
前言
今天这篇文章讲解的是哈希的另一种题型：字符串前缀哈希法，希望我的讲解你可以喜欢，谢谢 。
——————————————————————————————
? 字符串前缀哈希法： 核心思想：
字符串前缀哈希法是一种比较特殊的哈希方法，它是先预处理出所有字符串前缀的哈希，利用哈希数组进行存储，下标是0开始的，h[0]是等于0的 。
例如：
字符串“”
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=
Q=264;
这里取Q=264,这里可以直接定义哈希数组为 long long ，它会使超过264的数溢出，溢出的值就等价于对264取模 。
好处：利用前面算的前缀哈希可以求出任意一段的子串的哈希值 。
如图上面的这个图：
我们已知: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
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
代码：
#include #include using namespace std;typedef unsigned long long ULL;//将P和Q设定的非常好，就可以极大概率避免冲突（99.999%）：//P=131or13331const 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