转载请注明出处：https://hts0000.github.io/

欢迎与我联系：hts_0000@sina.com

什么是RK算法？

RK算法是一种字符串匹配算法。核心思想是将字符串映射为其字符集长度的数值(hash值)，将字符串比较变为数值比较，从而可以获得较好的性能。需要注意的是，当hash相同时，字符串任然有小概率不相同，hash不同则不可能相同。

对于文本串s和模式串p，我们计算p的hash值，然后再计算s中长度为len(p)的所有子串的hash值，对比他们是否相同，如果相同还需再比较一次字符串是否相同。

什么是hash值？

通过一个hash函数，将输入内容转化为数字，这个数字就是hash值。对于输入的内容相同，hash函数输出的值必须相同且应该尽量唯一。

如何计算字符串的hash值？

对于一串数字字符串"1234"，我们可以把它看做是10进制数，通过计算:'1'*10^(4-1) + '2'*10^(4-2) + '3'*10^(4-3)+'4'*10^(4-4)将它hash为1234(10^2表示10的2次方,4为字符串长度)。

对于小写字母字符串"abcd"，我们可以把它看做是26进制数，通过计算:'a'*26^(4-1) + 'b'*26^(4-2) + 'c'*26^(4-3) + 'd'*26^(4-4)将它hash为19010(‘a’=1,‘b’=2,‘c’=3,’d’=4)。

对于大小写字符混合字符串"AbCd"，我们可以把它看做是128进制(ASCII码128个字符)，通过计算:'A'*128^(4-1) + 'b'*128^(4-2) + 'C'*128^(4-3) + 'd'*128^(4-4)，将它们hash为137,929,188(‘A’=65,‘b’=98,‘C’=67,’d’=100)。

通过上述例子可以发现，我们可以把一串字符hash为它们字符集进制的数，那么我们是否可以用Unicode字符集作为进制数？不就可以表示所有字符了？答案是可以的。Unicode字符集所有字符个数为1114112个。

如何使用hash进行字符串匹配？

对于文本串s"12345"，我们希望知道模式串p"45"是否被s包含要如何做？

以10进制为例。

首先对p进行hash，'4'*10+'5'=45，对s[0:2]进行hash，'1'*10+'2'=12，12不等于45，进行下一轮计算s[1:3]。下一轮计算难道又要'2'*10+'3'=23这样遍历s[1:3]的每一个字符吗？其实不用，我们可以把(12-10)*10+3，这意味着我们总共只需要遍历s串一次，而p串也是一次，这就是rk算法时间复杂度O(m+n)的原因。

常用的字符串hash函数

BKDRHash

如何解决hash值相同但字符串不相同的情况

字符串hash难免出现hash值相同的情况，当相同时我们需要额外遍历一遍以确保相同。

Golang中的RK算法应用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// PrimeRK相当于我们上面提到的进制
const PrimeRK = 16777619

// HashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func HashStr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		// 将模式串hash为PrimeRK进制的数
		hash = hash*PrimeRK + uint32(sep[i])
	}
	// 
	var pow, sq uint32 = 1, PrimeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		sq *= sq
	}
	return hash, pow
}

// IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
// first occurrence of substr in s, or -1 if not present.
func IndexRabinKarp(s, substr string) int {
    if len(s) < len(substr) {
        return -1
    }
	// Rabin-Karp search
	hashss, pow := HashStr(substr)
	n := len(substr)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*PrimeRK + uint32(s[i])
	}
	if h == hashss && s[:n] == substr {
		return 0
	}
	for i := n; i < len(s); {
		h *= PrimeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashss && s[i-n:i] == substr {
			return i - n
		}
	}
	return -1
}

参考：https://www.cnblogs.com/golove/p/3234673.html