Rabin Karp算法模运算正确用法及LeetCode 187问题排查

问题 #

我尝试用带滚动哈希的Rabin Karp算法解决LeetCode 187. 重复的DNA序列问题。最初采用小端（little endian）方式实现，未使用任何MOD运算，代码可正常运行。但参考大端（big endian）实现方案并加入MOD运算后，无法得到正确结果，以下是我的实现代码，请问模运算环节我遗漏了什么？

初始无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) 

加入MOD运算后的代码 #

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)  

问题分析与修复 #

你的代码在模运算环节存在两个核心问题：

1. 滚动哈希更新逻辑顺序错误
   大端模式下，滚动哈希的正确更新逻辑是：先移除最左侧字符的权重（ord(text[index-1]) * prime^(L-1)），再将剩余哈希值整体左移（乘以prime），最后加入新的最右侧字符的权重。你当前代码先执行old_hash * prime再减左侧字符权重，导致左侧字符的权重被多乘了一次prime，完全偏离正确哈希值。

2. 负数模运算未处理
   当old_hash - ord(text[index-1]) * p_power结果为负数时，直接取模会得到负数哈希值，导致后续匹配错误，需要额外处理确保哈希值非负。

修复后的代码 #

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 - ord(text[index - 1]) * p_power) % MOD
        # 整体左移（乘prime）后加入新字符权重
        new_hash = (new_hash * prime + ord(text[index + L - 1])) % MOD
        # 确保哈希值非负
        return new_hash if new_hash >= 0 else new_hash + MOD

    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)  

额外优化建议 #

• DNA序列仅包含A/C/G/T四种字符，可将字符映射为0-3的整数，缩小哈希计算的数值范围，降低碰撞概率同时提升效率。
• 预先计算pow(prime, L-1, MOD)，避免每次滚动哈希时重复计算。

内容的提问来源于stack exchange，提问作者Setu Kumar Basak