字符串哈希
字符串哈希
问题描述
将字符串映射为整数，使得：
- 相同的字符串映射到相同的整数
- 不同的字符串尽量映射到不同的整数
- 能够快速计算子串的哈希值
字符串哈希算法
算法思想
- 选择一个大质数作为模数
- 选择一个进制数
(通常为131或13331)
- 将字符串看作
取模
- 使用前缀和思想预处理子串哈希值
时间复杂度
- 预处理时间：
- 查询时间：
- 空间复杂度：
代码实现
class StringHash {
private:
const int P = 131;
const long long M = 1e9 + 7;
vector<long long> h, p;
public:
StringHash(string& s) {
int n = s.length();
h.resize(n + 1);
p.resize(n + 1);
// 初始化次方数组
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = (p[i-1] * P) % M;
}
// 计算前缀哈希
h[0] = 0;
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * P + s[i-1]) % M;
}
}
// 计算子串[l,r)的哈希值
long long getSubstringHash(int l, int r) {
return ((h[r] - h[l] * p[r-l]) % M + M) % M;
}
};
class StringHash {
private final int P = 131;
private final long M = 1000000007;
private long[] h, p;
public StringHash(String s) {
int n = s.length();
h = new long[n + 1];
p = new long[n + 1];
// 初始化次方数组
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = (p[i-1] * P) % M;
}
// 计算前缀哈希
h[0] = 0;
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * P + s.charAt(i-1)) % M;
}
}
// 计算子串[l,r)的哈希值
public long getSubstringHash(int l, int r) {
return ((h[r] - h[l] * p[r-l]) % M + M) % M;
}
}
class StringHash:
def __init__(self, s: str):
self.P = 131
self.M = 10**9 + 7
n = len(s)
# 初始化次方数组
self.p = [0] * (n + 1)
self.p[0] = 1
for i in range(1, n + 1):
self.p[i] = (self.p[i-1] * self.P) % self.M
# 计算前缀哈希
self.h = [0] * (n + 1)
for i in range(1, n + 1):
self.h[i] = (self.h[i-1] * self.P + ord(s[i-1])) % self.M
# 计算子串[l,r)的哈希值
def getSubstringHash(self, l: int, r: int) -> int:
return ((self.h[r] - self.h[l] * self.p[r-l]) % self.M + self.M) % self.M
双哈希
为了降低哈希冲突的概率，可以使用两个不同的哈希函数：
- 选择两组不同的
- 同时计算两个哈希值
- 只有两个哈希值都相同时才认为字符串相同
应用场景
- 快速判断子串是否相同
- 字符串去重
- 最长回文子串
- 重复子串检测
- 字符串匹配
注意事项
- 选择合适的模数和进制
- 处理整数溢出
- 哈希冲突的处理
- 空串的处理
- 字符串长度的限制
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
查看11道真题和解析
