Rabin Karp算法中如何正确使用Modulo？

Question

我正在尝试解决leetcode问题187。使用 Rabin Karp 算法和滚动哈希方法重复 DNA 序列。起初，我没有使用任何 MOD 操作就解决了这个问题，如下所示。

class Solution:
    def calculate_hash(self, prime, text):
        hash_value = 0
        for i in range(len(text)):
            hash_value = hash_value + (ord(text[i]) * pow(prime, i))

        return hash_value

    def recalculate_hash(self, prime, old_hash, text, index, L):
        new_hash = old_hash - ord(text[index - 1])
        new_hash /= prime
        new_hash = new_hash + (ord(text[index + L - 1]) * pow(prime, L - 1))

        return new_hash 


    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L, s_len = 10, len(s)
        if s_len <= L:
            return []

        prime = 7
        seen, res = set(), set()
        
        old_hash = self.calculate_hash(prime, s[0:L])
        seen.add(old_hash)

        for i in range(1, s_len - L + 1):
            new_hash = self.recalculate_hash(prime, old_hash, s, i, L)
            if new_hash in seen:
                res.add(s[i:i+L])
            seen.add(new_hash)
            old_hash = new_hash    


        return list(res) 

在上面的方法中，我使用了小端方法，并且在计算滚动哈希值时必须使用除法。然而，我在 StackOverlow 中遇到了这个answer，其中建议使用大端方法，如下所示。

我尝试应用该方法，但没有得到想要的答案。这是我尝试过的代码。

class Solution:
    def calculate_hash(self, prime, text, L, MOD):
        hash_value = 0 
        for i in range(len(text)):
            p_power = pow(prime, L - i - 1, MOD)
            hash_value = (hash_value + (ord(text[i]) * p_power)) % MOD

        return hash_value

    def recalculate_hash(self, prime, old_hash, text, index, L, MOD):
        p_power = pow(prime, L - 1, MOD)
        new_hash = (old_hash * prime)
        new_hash = (new_hash - (ord(text[index - 1]) * p_power) + ord(text[index + L - 1])) % MOD

        return new_hash 


    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L, s_len = 10, len(s)
        if s_len <= L:
            return []

        prime = 7
        MOD = 2**31 - 1
        seen, res = set(), set()
        
        old_hash = self.calculate_hash(prime, s[0:L], L, MOD)
        seen.add(old_hash)

        for i in range(1, s_len - L + 1):
            new_hash = self.recalculate_hash(prime, old_hash, s, i, L, MOD)
            if new_hash in seen:
                res.add(s[i:i+L])
            seen.add(new_hash)
            old_hash = new_hash    


        return list(res)  

在 MOD 计算过程中我错过了什么？

Answer 1

def recalculate_hash(self, prime, old_hash, text, index, L, MOD):
    p_power = pow(prime, L - 1, MOD)
    new_hash = (old_hash * prime)
    new_hash = (new_hash - (ord(text[index - 1]) * p_power) + ord(text[index + L - 1])) % MOD

    return new_hash

当您需要减去它时，

ord(text[index - 1])

的幂实际上是

L

，因为前面的行已经将其“向上移动”了1。因此，

pow(prime, L - 1, MOD)

应为

pow(prime, L, MOD)

- 或者，您可以保留

pow(prime, L - 1, MOD)

，但在

乘以 

ord(text[index - 1]) * p_power之前减去 prime。

顺便说一句，在

calculate_hash

中，你不需要每次都从头开始计算幂，你可以在每次迭代中迭代乘以

prime

，与

recalculate_hash

中相同。