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

欢迎加微信交流与吐槽



blog comments powered by Disqus。如果你看不到评论框,加我微信或者自己想办法。