字符串哈希
分析
也是很简单但很精妙的算法
进制转换的内容 在复习过二进制后已经很熟悉了
这个字符串哈希就是仿用了P进制换10进制的方式实现的
P取经验值 131 所以可以记成是一个 131进制的数转变成10进制(把字符串当成一个131进制数）
模上\(2^{64}\)其实就等价于一个8字节的东西溢出 对 直接用unsigned long long存 将本该是问题的溢出巧妙转变成对\(2^{64}\)取模
然后我们就可以处理出所有字符串的一个哈希值
为了求某一段该怎么办
显然 这是前缀和问题
那么 我们可以用上面的方法 预处理出所有前缀字符串的哈希值的前缀和数组
要求某一段该怎么办
用s[r]-s[l]
发现并不对应 错了几位 所以得把前缀（l）部分 左移到与r 的高位匹配位置上去（后几位补0）
左移怎么做呢 左移一次就是*p其实（这点在二进制里也讲的很清楚了）
左移两位就是\(*p^2\)以此类推
那么要让l与r对齐 实际上是要左移r-l+1位
也就是我们要快速求到\(p^{r-l+1}\)
而每一位其实也是乘上一个p的n次方
所以我们完全也可以把p预处理出来
构造前缀和数组就成了这样
把上一个记录的值左移一位 然后加上当前位 就是截止当前位的哈希值
它用途比较广泛 不像kmp、trie那么具有鲜明特色（循环结、多次匹配、前缀匹配）
要说有非他不能解决的问题 那就是截取两段区间 问是否相等 这样的问题
它这种方式本质上是会有冲突的 只不过通过一些经验值 使得它能在大多数情况下不会发生冲突
用它解决问题的话可以不用想太多 直接当做是可行的 如果两串字符串最后的哈希值不一样就认为是不同的 直接水掉 所以它这种匹配方式很方便 可以解决大多数问题
代码实现也很简单
用ULL存 解决映射问题
在读入时就预处理好P的n次方和字符串哈希的前缀和
处理匹配问题只需要 用h[r]-h[l-1]*p[r-l+1]即可 理解这个移位过程就好说
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;
char str[N];
ULL h[N],p[N];
int n,m;
ULL get(ULL h[],int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
cin>>n>>m;
cin>>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;
cin>>l1>>r1>>l2>>r2;
if(get(h,l1,r1)==get(h,l2,r2))
puts("Yes");
else
puts("No");
}
return 0;
}
题目：
字符串哈希
更多题目：
💬 评论