天津最好网站建设公司,做产品网站要备案吗,做网站栏目是什么意思,濮阳做网站优化字符串Hash就是构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应#xff0c;也就是#xff0c;一个字符串对应一个数字#xff0c;那么一个数字也对应一个字符串。 用字符串Hash的目的是#xff0c;我们如果要比较一个字符串#xff0c;我们不用直接比…字符串Hash就是构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应也就是一个字符串对应一个数字那么一个数字也对应一个字符串。 用字符串Hash的目的是我们如果要比较一个字符串我们不用直接比较字符串而是比较它对应映射的数字这样子就知道两个“子串”是否相等。从而达到子串的Hash值的时间为 O(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
关键点 字符串哈希值的计算通过前缀哈希值可以在常数时间内计算任意子串的哈希值。在这里使用了 get 函数来计算 [l, r] 子串的哈希值。
进制选择选择一个适当的进制是关键这里使用了常用的质数 131 常用P 还可以 133313。质数的选择可以减小哈希冲突的可能性。前缀哈希值的快速计算通过累积进制的幂可以在常数时间内计算前缀哈希值。这里使用了 p 数组存储进制的幂h 数组存储前缀哈希值。字符串比较通过比较两个子串的哈希值是否相等可以在常数时间内完成字符串的比较。这在一些算法中能够提高效率例如字符串的快速匹配等。#include iostreamusing namespace std;typedef unsigned long long ULL; // 使用 unsigned long long 类型表示哈希值const int N 100010, P 131; // N 表示字符串长度的最大值P 是选择的哈希进制int n, m;
ULL h[N], p[N]; // h 存储前缀哈希值p 存储进制的幂
char str[N]; // 输入的字符串ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l 1]; // 计算字符串 [l, r] 的哈希值使用前缀哈希值的差值表示子串哈希值
}int main()
{scanf(%d%d%s, n, m, str 1);p[0] 1;for(int i 1; i n; i ){p[i] p[i - 1] * P; // 计算进制的幂h[i] h[i - 1] * P str[i]; // 计算前缀哈希值}while(m -- ){int l1, r1, l2, r2;scanf(%d%d%d%d, l1, r1, l2, r2);if(get(l1, r1) get(l2, r2)) printf(Yes\n); // 比较两个子串的哈希值是否相等else printf(No\n);}return 0;
}
代码中 h[i] h[i - 1] * P str[i];是字符串哈希的递推计算方式称为Rolling Hash。
在这个式子中h[i] 表示字符串的前 i 个字符的哈希值。它通过前一个状态 h[i-1]乘以进制 P再加上当前字符 str[i] 的 ASCII 码得到当前状态 h[i]。
这个计算过程实际上是一种累积计算每次迭代都基于前一个状态进行更新。由于使用了进制 P每一次迭代都相当于在前一个状态的基础上左移一位并加上新字符的贡献。
这样计算的好处在于每次只需要常数时间就能够更新哈希值使得整个字符串的哈希值的计算复杂度是线性的。在很多字符串匹配、子串比较的算法中这种哈希计算方式可以提高效率。需要注意的是为了避免整数溢出通常需要选择一个适当的大质数作为进制 P。
