Golang源码剖析——字符串查找算法

08 August 2014

发现好多笔试题，都问的是库函数。

发现好多笔试题，都问的是库函数。往简单的做，有效率不太高的算法，往复杂的做，就得看源码了。

写一个在一个字符串（n）中寻找一个子串（m）第一个位置的函数

暴力字符串匹配方法（Brute forceing matching）。这个写法不难，复杂度O(n*m)。

func IndexFuck(s, sep string) int {
	for i := 0; i < len(s); i++ {
		if s[i] == sep[0] {
			is := true
			j := 0
			for ; j < len(sep); j++ {
				if sep[j] != s[i] {
					is = false
					break
				}
			}
			if is {
				return i
			}
		}
	}
	return -1
}

Rabin-Karp算法，能把复杂度最小减到O(n)。设要匹配的子串为sep，查找的字符串为s。通过一个哈希算法，把sep哈希成一个数字，以sep的长度，依次遍历s中长度和sep相同的串，直到计算出的值是相等的。

计算哈希的方法是，把原本的字符串看作是一种E进制的编码，然后将该编码转成10进制用数字表示。Golang用16777619作为该进制数。（这是我的理解，至于为什么选择这个整数，我也不是很清楚，只不过发现很多哈希算法都用过这个神奇的数字16777619 = (2^24 + 403)）。

举个例子，原始串s是12345，匹配串sep是45。第一次用12和45比较计算出串的哈希值，1*E+2 != 4*E+5。然后计算23和45的值。

这里有一个问题，如果要匹配的字串长度比较长，是1000位，那么，每一次匹配都得对这1000位进行计算。这时的复杂度就是O(n*m)了，而且还需要计算，这比暴力判断算法还要复杂。仔细观察，发现每次计算的长度的都一样，而且是依次进行的，前后两个串12和23有共同部分2，如果子串sep长度是1000，那么前后两次子串的共同部分就是999的长度了。所以，只需要保留共同部分，把前面的头去掉，后面的尾补上，就能够完成新串的计算。

上面的例子，(1*E+2)*E+3-1*E*E = 2*E+3。如此一来，一个简单的运算，就能够得到新串的哈希值。Golang里面strings包的实现：

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 = 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
		}
		// 只有32位，超出范围的会被丢掉
		sq *= sq
	}
	return hash, pow
}

func Index(s, sep string) int {
	n := len(sep)
	// Hash sep.
	hashsep, pow := hashstr(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])
	}
	if h == hashsep && s[:n] == sep {
		return 0
	}
	for i := n; i < len(s); {
		h *= primeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashsep && s[i-n:i] == sep {
			return i - n
		}
	}
	return -1
}

最后面的for循环，i表示计算新串新加的字符，也就是例子里面的3。所以，i-n+1就是新串的头地址。

一般，按照这种算法算出的值都会超过整形的范围。上面的16777619，计算一下平方就超unit32的范围了。常用的做法，是再取一个比较大的质数，求余，用余数作为哈希值。这样就能保证高位不会被截取丢弃了。而Golang包里的代码是不操作，直接丢弃，太霸气了。

本文所涉及到的完整源码请参考。

参考文献

原文链接：Golang源码剖析——字符串查找算法，转载请注明来源！

–EOF–

Golang 50