Rabin–Karp

字符串

说明

滚动更新窗口哈希并在哈希相同时核对原文；平均接近 O(n+m)。

分析

模式和当前文本窗口先计算模哈希，窗口右移时从哈希中移除旧字符并加入新字符。哈希不同时可立即排除，哈希相同时必须比较原文以防碰撞。

图解推演

对 hello gopher，每个长度 6 的窗口先比较哈希；到起点 6 时窗口为 gopher，哈希相同后再核对六个字节，才返回 6。哈希不相同能直接排除，相同只是候选。大量碰撞时反复做原文比较，最坏仍可达 O(nm)。

查看图表代码

适用前提与边界

平均性能良好，但恶意碰撞可能让最坏时间退化。

示例输入与调用

fmt.Println(RabinKarp("hello gopher", "gopher"))

运行输出

6

完整 Go 示例

package main

import "fmt"

func RabinKarp(text, pattern string) int {
	m := len(pattern)
	if m == 0 {
		return 0
	}
	if m > len(text) {
		return -1
	}
	const base, mod = 256, 1000000007
	power, ph, th := 1, 0, 0
	for i := 0; i < m; i++ {
		ph = (ph*base + int(pattern[i])) % mod
		th = (th*base + int(text[i])) % mod
		if i < m-1 {
			power = power * base % mod
		}
	}
	for i := 0; i+m <= len(text); i++ {
		if ph == th && text[i:i+m] == pattern {
			return i
		}
		if i+m < len(text) {
			th = ((th-int(text[i])*power%mod+mod)*base + int(text[i+m])) % mod
		}
	}
	return -1
}

func main() {
	fmt.Println(RabinKarp("hello gopher", "gopher"))
}