Rabin Karp 算法
Rabin Karp 算法，简称 RK 算法，是由 Michael Oser Rabin 和 Richard Manning Karp 在1987 年提出的字符串搜索算法。该算法主要用于在文本中搜索单个模式串的位置，其基于哈希函数的原理，将字符串和模式都映射为一个整数值，并通过比较这些整数值来确定它们是否匹配。
基本思想
哈希函数的使用：Rabin Karp 算法将字符串和模式都视为数字（例如，将它们看作字符编码的值），然后使用哈希函数来计算它们的哈希值。
滚动哈希算法：在 RK 算法中，一个重要的步骤是滚动哈希算法，它允许我们快速计算文本串中每个子串的哈希值，而不需要重新计算整个子串的哈希值。这大大提高了算法的效率。
算法步骤
- 预处理： 计算模式串 p 的哈希值 hash_p。 计算文本串 T 中每个长度为 m（模式串长度）的子串的哈希值，并将它们与hash_p 进行比较。
- 匹配过程： 对于文本串 T 中的每个子串，如果其哈希值与 hash_p相等，则进一步检查子串和模式串是否完全匹配（以避免哈希冲突）。 如果哈希值不同，则直接跳过该子串，继续向后匹配。如果找到匹配的子串，则返回其起始位置。 如果遍历完整个文本串仍未找到匹配项，则返回 -1。
滚动哈希算法
在 Rabin-Karp（RK）算法中，滚动哈希（Rolling Hash）是一个重要的概念，用于高效地计算字符串的哈希值，特别是在处理字符串的子串匹配问题时。滚动哈希允许我们在 O(1) 时间复杂度内将哈希值从一个子串更新到其相邻的子串，这使得 RK 算法在处理文本搜索时非常高效。
下面我们用一个例子来解释一下这种算法思想。
PYTHON代码实现说明
def rabinKarp(T: str, p: str, d: int, q: int) -> int:
n, m = len(T), len(p)
if n < m:
return -1 # 如果文本串长度小于模式串长度，直接返回-1
hash_p, hash_t = 0, 0
for i in range(m):
# 计算模式串 p 的哈希值，假设d为256
hash_p = (hash_p * d + ord(p[i])) % q #这里就是实现几次方，345就是3*256的二次方+4*256加5*256的0次方
# 计算文本串 T 中第一个子串的哈希值 其中ord（）代表将值变成ASCII值
hash_t = (hash_t * d + ord(T[i])) % q #当hash_t hash_p过大时，q会生效，q一般是比较大，防止数值溢出
power = pow(d, m - 1, q) # 使用模幂运算，避免大数溢出 d 的 m-1 次方对 q 取模的结果
for i in range(n - m + 1): #这里是n-m+1 是因为如果文本字符串长度为5， 搜索的字符串长度为3，那就是有5-3+1=3种可能
if hash_p == hash_t: # 检查哈希值是否相等
# 如果哈希值相等，验证模式串和子串每个字符是否完全相同
if T[i:i + m] == p: # 使用切片比较，避免额外的循环
print( i ) #识别正确，打印位置值
# 计算下一个相邻子串的哈希值
if i < n - m:
# 移除字符 T[i] 的哈希值贡献，这里滚动哈希
hash_t = (hash_t - power * ord(T[i])) % q
# 如果 hash_t 为负，则加上 q 使其非负
if hash_t < 0:
hash_t += q
# 增加字符 T[i + m] 的哈希值贡献
hash_t = (hash_t * d + ord(T[i + m])) % q
print(rabinKarp("abddsadabdjehwqqiabdoliqweoabd","abd",25,10011)) //进行验证
0
7
17
27
总结
Rabin-Karp 算法在文本搜索、生物信息学（如 DNA 序列比对）、网络安全（如病毒检测）等领域有广泛应用。它特别适用于在大型文本数据集中快速查找模式串的场景。其次Rabin-Karp 算法是一种高效的字符串搜索算法，它通过哈希技术加速了搜索过程。该算法在大多数情况下表现良好，但需要注意处理哈希冲突和选择合适的哈希函数及参数。在适当的应用场景下，Rabin-Karp 算法可以显著提高字符串搜索的效率。
参考资料
文心一言
LeetCode 算法笔记（LeetCode-Notes）
自律每一天，fighting
标签：子串,Karp,hash,算法,哈希,Rabin From： https://blog.csdn.net/zsy54577/article/details/139805627