這個問題與rolling-hash非常相似，但是關于溢出/否定結果的一些細節對我來說仍然不清楚。我也檢查了這個 Rabin-Karp實現，并且對下面的行有疑問：txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;我了解以下表達式可能會給出否定結果：txtHash - RM*txt.charAt(i-M)第一個問題：如果我們總是添加 Q，一個大素數，這個結果是否會由于溢出而導致負數？如果不是，為什么不呢？如果是，是否應該僅在結果為負時才進行此添加？第二個問題：如果我們暫時不關心負數，寫下面的表達式是否正確？txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;第三個問題，這部分最讓我困惑：讓我們假設當我們添加 Q 時不會發生溢出。為什么在前導數字上有最左邊的 % Q 操作？txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;我已經閱讀了我鏈接的答案，并根據 Aneesh 的答案，如果我理解正確，下面的表達式應該是相似的：hash = hash - ((5 % p)*(10^2 %p) %p)txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;但我不明白為什么它們相似，因為在哈希示例中，% p 不是針對先前的哈希值計算的，但是對于 txtHash，我們也計算了先前哈希的 % Q。
1 回答
慕田峪4524236
TA貢獻1875條經驗 獲得超5個贊
第一個問題：
如果我們總是添加 Q，一個大素數，這個結果是否會由于溢出而導致負數？如果不是，為什么不呢？如果是，是否應該僅在結果為負時才進行此添加？
通常選擇質數 Q 以使 2Q 仍然不會溢出類型。
現在讓我們看看。
txtHash是從 0 到 Q - 1。RM*txt.charAt(i-M)很大。RM*txt.charAt(i-M) % Q是從 0 到 Q - 1。txtHash - RM*txt.charAt(i-M) % Q是從 -(Q - 1) 到 Q - 1。txtHash + Q - RM*txt.charAt(i-M) % Q是從 1 到 2Q - 1。
所以，只要 2Q - 1 不溢出，上面的表達式就可以了。
第二個問題：
如果我們暫時不關心負數，寫下面的表達式是否正確？
txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;
是的，如果% Q總是給出從 0 到 Q-1 的結果（例如在 Python 中），上面的表達式就可以了。
第三個問題，這部分最讓我困惑：
讓我們假設當我們添加 Q 時不會發生溢出。為什么在前導數字上有最左邊的 % Q 操作？
txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;
假設我們刪除最左邊的% Q. 然后讓我們再次估計：
txtHash是從 0 到 Q - 1。RM*txt.charAt(i-M)很大。多大？從 0 到 (Q - 1) * CharCode。
txtHash - RM*txt.charAt(i-M)是從 -(Q - 1) * (CharCode - 1) 到 Q - 1。txtHash + Q - RM*txt.charAt(i-M)從 -(Q - 1) * (CharCode - 2) 到 2Q - 1。
仍然可能是負面的。不是我們想要的。
添加回答
舉報
0/150
提交
取消