滚动哈希

字符串

说明

移除旧字符并加入新字符以 O(1) 更新窗口哈希；需要防范哈希碰撞。

分析

预先计算最高位对应的权重，窗口右移时减去旧首字符的贡献，再乘以进制并加入新尾字符。这样每个窗口哈希只需常数时间。

图解推演

窗口 ban 的哈希可写成 b·B²+a·B+n。右移成 ana 时先减 b·B²，剩 a·B+n，再乘 B 并加 a，得到 a·B²+n·B+a，最后取模。双哈希仍有碰撞可能，要求严格相等时要比较原文；本例 int 中间乘积也要求足够位宽。

查看图表代码

适用前提与边界

模哈希会碰撞；双哈希只能降低概率，严格相等判断仍须二次比较原文。

示例输入与调用

fmt.Println(WindowHashes("banana", 3))

运行输出

[6497841 6435120 7290429 6435120]

完整 Go 示例

package main

import "fmt"

func WindowHashes(s string, k int) []int {
	if k <= 0 || k > len(s) {
		return nil
	}
	const base, mod = 257, 1000000007
	power, hash := 1, 0
	for i := 0; i < k; i++ {
		hash = (hash*base + int(s[i])) % mod
		if i < k-1 {
			power = power * base % mod
		}
	}
	out := []int{hash}
	for i := k; i < len(s); i++ {
		hash = ((hash-int(s[i-k])*power%mod+mod)*base + int(s[i])) % mod
		out = append(out, hash)
	}
	return out
}

func main() {
	fmt.Println(WindowHashes("banana", 3))
}