字符串哈希
用法：
- 用于解决字符串匹配问题 传统暴力匹配需要 n层for循环 时间复杂度会很大 但是字符串哈希 能 缩为O(n)时间复杂度
- 过程 构造一个p数组和一个哈希查询数组
- p数组是用来区间查询用的
- 哈希数组 是存储字符串的哈希值（理解为前缀和
- 如果字符串不同哈希值相同 叫哈希碰撞 所以p的取值就很关键
- p一般取131或者13331 能够防止碰撞
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int pp=131;或者13331
ull h[10005],p[1550];
char s[1550];
void init(){//初始化
p[0]=1;h[0]=0;
//n是字符串长度
for(int i=1;i<=n;i++){
p[i]=p[i-1]*p;//用来存p倍数
h[i]=h[i-1]*p+s[i];//前缀合
}
}
//区间查询函数
ull get(int l,int r){
//查【2，5】范围
return h[r]-h[l-1]*p[r-l+1];
h[5]-h[1]*p**4 因为多乘了4个p
}
原文地址：https://blog.csdn.net/2302_78926002/article/details/142700866
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！