Rabin-Karp字符串匹配算法实现问题：单字符查找哈希值异常

问题场景 #

测试用例：haystack="abc"，needle="c"，运行后输出如下：

hayHash: 0 and needleHash: 2 at i: 0 remove: a and add: b and new hash is before checking for negatives: 1

hayHash: 1 and needleHash: 2 at i: 1 remove: b and add: c and new hash is before checking for negatives: -50

hayHash: 51 and needleHash: 2

预期最后一次hayHash应为2（字符'c'的哈希值），但实际计算得到-50（修正后为51），导致哈希不匹配。

核心错误 #

代码中哈希权重hash的计算循环次数错误。

Rabin-Karp算法中，滑动窗口时需要计算的权重是d^(m-1) mod q（m为needle长度），用于移除窗口最左侧字符的哈希贡献。但你的代码中：

for (i in 0..needle.length)
    hash = (hash * d) % q

当needle.length=1时，这个循环会执行2次（0到1），最终计算出的是d^2 mod q，而非正确的d^(0)=1。

错误计算过程 #

• 初始hash=1，循环两次：
  1. 第一次循环：hash = (1*256) %101 = 256-2*101=54
  2. 第二次循环：hash=(54*256)%101=13824%101=88
• 最后一次滑动计算：
  hayHash = (256*(1 - 1*88) +2) %101 = (256*(-87)+2)%101 = (-22272+2)%101=-22270%101=-50

修正方案 #

将权重计算的循环次数改为m-1次（m为needle长度），确保得到正确的d^(m-1) mod q：

private fun find(haystack: String, needle: String): Int {
    if(needle.length > haystack.length) return -1

    val q = 101
    val d = 256
    var needleHash = 0
    var hayHash = 0
    var hash = 1
    val m = needle.length

    // 计算 d^(m-1) mod q，循环m-1次
    for (i in 1 until m)
        hash = (hash * d) % q

    for(i in 0..needle.lastIndex) {
        needleHash = (d * needleHash + (needle[i] - 'a')) % q
        hayHash = (d * hayHash + (haystack[i] - 'a')) % q
    }

    for(i in 0..(haystack.length - m)) {
        println("hayHash: $hayHash and needleHash: $needleHash")
        if(hayHash == needleHash) {
            var match = true
            for(j in 0..needle.lastIndex) {
                if(haystack[i + j] != needle[j]) {
                    match = false
                    break
                }
            }
            if(match) return i
        }
        if(i == haystack.length - m)
            break
        print("at i: $i remove: ${haystack[i]} and add: ${haystack[i + m]}")   
        hayHash = (d * (hayHash - (haystack[i]  - 'a') * hash) + (haystack[i + m]  - 'a')) % q
        println(" and new hash is before checking for negatives: $hayHash")
        if(hayHash < 0)
            hayHash += q
    }

    return -1
}

修正后验证 #

当m=1时，权重循环不执行，hash=1：

• 最后一次滑动计算：hayHash=(256*(1 -1*1)+2)%101=(0+2)%101=2，与needleHash相等，正确匹配到索引2。

内容的提问来源于stack exchange，提问作者CJR