发现好多笔试题，都问的是库函数。往简单的做，有效率不太高的算法，往复杂的做，就得看源码了。
写一个在一个字符串（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包里的代码是不操作，直接丢弃，太霸气了。
本文所涉及到的完整源码请参考。
参考文献
- 【1】图说Rabin-Karp字符串查找算法 - 图灵社区
- 【2】字符串匹配之Rabin-Karp算法 - lmx077
- 【3】Rabin-Karp 字符串搜索算法 - 貔貅
- 【4】Source file src/pkg/strings/strings.go - The Go Programming Language
原文链接：Golang源码剖析——字符串查找算法，转载请注明来源！
有疑问加站长微信联系（非本文作者）
