Rabin-Karp字符串匹配（Rolling hash）的实现

Question

我正在尝试实施 Rabin-Karp 字符串匹配算法以在字符串

needle

中查找字符串

haystack

（字符串

haystack

的返回索引，其中找到了字符串

needle

的匹配项）。我在试图在干草堆

c

中寻找针

abc

时遇到错误。

这是运行我的代码以在

c

中查找

abc

后我的输出的样子：

hayHash: 0 and needleHash: 2 at i: 0 remove: a and add: b and new hash 在检查底片之前：1

hayHash: 1 and needleHash: 2 at i: 1 remove: b and add: c 和 new hash 在检查底片之前：-50

hayHash：51 和 needleHash：2

我不明白为什么最后一次哈希重新计数计算为

-50

而不是

2

for

hayHash

。这里

hayHash

和

needleHash

应该是仅由字符

'c'

组成的计算哈希值，并且两者的值应该相同。但是我的代码正在将

hayHash

重新计算为

51

（取消负值之前的

-50

）而不是

2

.

对我的代码中可能存在的问题有什么建议吗？

这是我的代码：

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

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

    return -1
}

Answer 1

for (i in 0..needle.length)

初始化时

hash

是一个差一错误。你想要

for(i in 0..needle.lastIndex)

.

Answer 2

一部分是预先计算d的错误幂。 另一个是不仅将离开窗口的角色乘以这种能力，而且乘以与当前hayHash的差异。
试试

hayHash = (d * hayHash - ((haystack[i]  - 'a') * hash) + (haystack[i + needle.length] - 'a')) % q