02. Rabin Karp 算法

[giscus[bot]]

02. Rabin Karp 算法

1. Rabin Karp 算法介绍 Rabin Karp 算法：简称为 RK 算法。是由它的两位发明者 Michael Oser Rabin 和 Richard Manning Karp 的名字来命名的。RK 算法是他们在 1987 年提出的、使用哈希函数以在文本中搜寻单个模式串的字符串搜索算法。 - Rabin Karp 算法思想：对于给定文本串 ...

https://algo.itcharge.cn/06.String/02.String-Single-Pattern-Matching/02.String-Rabin-Karp/

[zaza0209]

谢谢作者的整理！中间好像有几行公式编译错误了

[HalfCheesee]

def rabinKarp(T: str, p: str, d: int, q: int) -> int:
    n, m = len(T), len(p)
    if n < m:
        return -1

    hash_p, hash_t = 0, 0

    h = 1
    for _ in range(m - 1):
        h = (h * d) % q

    for i in range(m):
        hash_p = (hash_p * d + ord(p[i])) % q
        hash_t = (hash_t * d + ord(T[i])) % q

    for i in range(n - m + 1):
        if hash_p == hash_t:
            if T[i:i+m] == p:
                return i

        if i < n - m:
            hash_t = ((hash_t - (ord(T[i]) * h) % q) * d + ord(T[i + m])) % q

    return -1