Lintcode strStr II函数异常：匹配失败且哈希值不一致求助

嘿，我看你在Lintcode刷strStr II的时候遇到了头疼的问题——明明源字符串里有"bcd"，但程序输出-1而不是预期的1，调试发现是相同的子串哈希值对不上。这大概率是Rabin-Karp滚动哈希的实现细节出了问题，我帮你排查几个高频出错点：

1. Power值计算有没有漏取模？ #

你的代码里初始化power = 1然后循环m-1次，理论上是要算出base^(m-1)，但如果循环里只做power *= base而没取模，数值会爆炸式增长（比如base=1e6，m=3的话power会变成1e12），后续计算哈希时很容易出现溢出或者逻辑错误。正确的做法应该是每次乘完都对一个大质数取模，比如：

power = (power * base) % mod

2. 哈希计算的顺序和取模逻辑错了吗？ #

目标字符串的哈希计算必须是累积乘base再加字符ASCII值的顺序，比如：

target_hash = 0
for c in target:
    target_hash = (target_hash * base + ord(c)) % mod

源字符串的滚动哈希也要严格遵循这个逻辑：初始窗口的哈希要和目标的计算方式一致，滚动时先减去左边字符的贡献（ord(source[i-m]) * power），再乘base加上新字符的ASCII值，而且每一步都要取模，还要处理负数（因为减法可能得到负数值，得加mod再取模）：

current_hash = (current_hash - ord(source[i - m]) * power) % mod
current_hash = (current_hash + mod) % mod  # 处理负数
current_hash = (current_hash * base + ord(source[i])) % mod

如果顺序搞反（比如先加再乘），或者漏了取模，相同的字符串哈希值肯定对不上。

3. 是不是没给哈希加“模数（mod）”？ #

你代码里只定义了base = 1000000，但没定义mod（比如选10**9+7这种大质数）。虽然Python支持大整数，但不用mod的话，哈希值会变得无比巨大，不仅计算效率低，还可能因为某些隐式的数值处理导致哈希值不匹配。加mod能把哈希值限制在合理范围，避免这些问题。

4. 初始窗口的哈希计算正确吗？ #

比如源字符串前m个字符的哈希，是不是和目标字符串的哈希计算逻辑完全一致？如果初始窗口算错了，后面滚动的时候肯定也会跟着错。

给你一个修正后的完整代码参考，你可以对照自己的代码找差异：

def strStr2(self, source, target):
    if source is None or target is None:
        return -1
    m = len(target)
    if m == 0:
        return 0
    n = len(source)
    if n < m:
        return -1
    
    base = 10**6
    mod = 10**9 + 7
    power = 1
    # 计算base^(m-1) mod mod
    for _ in range(m-1):
        power = (power * base) % mod
    
    # 计算目标字符串的哈希
    target_hash = 0
    for c in target:
        target_hash = (target_hash * base + ord(c)) % mod
    
    # 计算源字符串初始窗口的哈希
    current_hash = 0
    for i in range(m):
        current_hash = (current_hash * base + ord(source[i])) % mod
    
    if current_hash == target_hash:
        return 0
    
    # 滚动哈希遍历
    for i in range(m, n):
        # 移除窗口左边字符的贡献
        current_hash = (current_hash - ord(source[i - m]) * power) % mod
        # 处理负数情况
        if current_hash < 0:
            current_hash += mod
        # 添加新字符到窗口
        current_hash = (current_hash * base + ord(source[i])) % mod
        
        # 哈希匹配后再做一次字符串比对，避免哈希冲突
        if current_hash == target_hash and source[i - m + 1:i + 1] == target:
            return i - m + 1
    
    return -1

另外提一句：就算哈希值匹配，最好再做一次实际的字符串比对，因为哈希冲突是小概率但存在的情况，这能保证结果100%正确。

你可以先检查自己的代码有没有上述这些问题，尤其是取模和滚动哈希的计算逻辑，应该就能解决问题啦！

内容的提问来源于stack exchange，提问作者Greedy.W