我有這個 Rabin Karp 實作。現在我為滾動哈希做的唯一一件事就是power*source[i]從sourceHash. power是31^target.size()-1 % mod
，但我不明白為什么我們加入mod到sourceHash當它變為負值。我曾嘗試添加其他值，但它不起作用，并且僅在我們添加mod. 為什么是這樣？我們添加mod而不是其他任何東西（例如隨機大數）是否有特定原因。
int rbk(string source, string target){
int m = target.size();
int n = source.size();
int mod = 128;
int prime = 11;
int power = 1;
int targetHash = 0, sourceHash = 0;
for(int i = 0; i < m - 1; i ){
power =(power*prime) % mod;
}
for(int i = 0; i < target.size(); i ){
sourceHash = (sourceHash*prime source[i]) % mod;
targetHash = (targetHash*prime target[i]) % mod;
}
for(int i = 0; i < n-m 1; i ){
if(targetHash == sourceHash){
bool flag = true;
for(int j = 0; j < m; j ){
if(source[i j] != target[j]){
flag = false;
break;
}
}
if(flag){
return 1;
}
}
if(i < n-m){
sourceHash = (prime*(sourceHash - source[i]*power) source[i m]) % mod;
if(sourceHash < 0){
sourceHash = mod;
}
}
}
return -1;
}
uj5u.com熱心網友回復：
使用模算術時，(mod n)我們只有n 不同的數字：0, 1, 2, ..., n - 1. out of 的所有其他數字0 .. n - 1都等于 in 中的某個數字0 .. n - 1：
-n ~ 0
-n 1 ~ 1
-n 2 ~ 2
...
-2 ~ n - 2
-1 ~ n - 1
或者
n ~ 0
n 1 ~ 1
n 2 ~ 2
...
2 * n ~ 0
2 * n 1 ~ 0
在一般情況下，A ~ B當且僅當(A - B) % n = 0（此處%代表余數）。
在實作 Rabin Karp 演算法時，我們可能會遇到兩個潛在的問題：
- 哈希可能太大，我們可能會面臨整數溢位
- 負余數可以在不同的編譯器上以不同的方式實作：
-5 % 3 == -2 == 1
為了解決這兩個問題，我們可以對余數進行歸一化，并且只對安全 0 .. n - 1范圍內的數字進行操作。對于任意值，A我們可以把
A = (A % n n) % n;
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/380757.html
下一篇：計算給定字串出現次數的函式