我正在尝试实现 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 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
我不明白为什么最后一次哈希重新计数计算为 -50
而不是2
对于 hayHash
。这里都是hayHash
和needleHash
应该是仅包含 char '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
}
最佳答案
初始化 hash
时
for (i in 0..needle.length)
是一个差一错误。您需要 for(i in 0..needle.lastIndex)
。
关于algorithm - Rabin-Karp字符串匹配的实现(滚动哈希),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/75626337/