字符串查找是在程序中经常会用到的一个功能。所有语言的类库都会实现这个功能。这也要求在查找算法上要有高效率的表现。
那么如何做到高效的查找字符串呢？我们来探秘一下。
两种算法
Brute ForceRabin-Karp在 Golang 的字符串查找中，两种算法都有用到。这和这两种算法在不同的场景下的优势不同有很大关系。我们可以先来看一下这两种算法的原理是什么，然后再对照到 Golang 的源码中。
Brute Force
这种算法其实就是最简单的一个个的字符去做对比来判断字符串是否一样。这种算法的特点就是实现简单，但是相应的效率也不是很高。
主串模式串如果，我们要在 A 中查找B，那么我们就需要从 编号为 0 开始的地方，一直到 n-m 的地方，将 m 长度的子串和 B 对比，看看是否相同。那么，也就是要对比 次，每次对比 m 个字符，换算成公式就是： ( n − 1 ) ∗ m ，所以，这个算法的时间复杂度就是 O ( n ∗ m ) 。
这样的时间复杂度实在不是一个高效的实现，但实际中还是有很多地方使用这种算法（比如 Golang），究其原因就是因为两个：一是简单的算法实现容易，也比较容易理解，有问题方便排查；二是实际情况中，会出现这么性能差的时候从概率上是比较小的。
假设我们有一个字符串是 "xxxxxxxx.......xxxxx" ，我们要在这个主串中，查找模式串 “xxxxxxy”，在这种情况下，算法就会退化到最差的时间复杂度上面。但实际上这种情况会非常少。
Rabin-Karp
那么如果真的出现了上面的算法的最坏情况，怎么办呢？我们就可以使用这种加强版的算法来避免 BF 算法退化到最差的情况。
模式串主串
那么，如果要用哈希算法的话，就会遇到几个问题：
- 如何解决哈希冲突的问题？
- 主串中的每一个子串都需要计算哈希值，效率如何提高？
问题一：如何解决哈希冲突的问题
哈希冲突是一定会出现的情况，解决的方法在这个算法里非常简单，直接再对比一下字符串本身就可以了。如果哈希不匹配，就不需要对比字符串本身。
问题二：如何解决计算哈希效率的问题
这个问题需要哈希计算的函数实现非常有技巧才行。
我们假设要匹配的字符串的字符集中只包含 X 个字符，我们可以用一个 X 进制数来表示一个子串，尝试将一个字符串的每一个字符计算一个基础的哈希值，然后再乘以所在的位置，最后将所有的值加起来，最后将这个 X 进制数转化成十进制数，作为子串的哈希值。
为了问题可以更简单的描述，我们假设我们的字符串中只有26个英文字母，就用26进制来表示一个字符串，所以 2 6 。从 a ~ z，我们将其表示为 0 ~ 25。字母和数字一一对应。
所以，当我们要计算上面的字符串匹配的时候，就可以这样算。每个字母对应的数字再乘以它进制的位置，然后相加就可以得出哈希值。
Hash("test") = 19 * 26 * 26 * 26 + 4 * 26 * 26 + 18 * 26 + 19 * 1 = 337135
Hash("this") = 19 * 26 * 26 * 26 + 7 * 26 * 26 + 8 * 26 + 18 * 1 = 338902
模式串那么，如何解决效率问题呢？
26 * 26 * 26比如上面的例子中。计算位置1开始的子串只需要使用：
Hash("hisi") = (338902 - 19*26*26*26) *26 + 8 * 1 = 128916
这样，计算哈希就会非常高效。
Golang 中的字符串查找
stringsstrings.Index()Index()BF算法RK算法RK算法下面，我们对照一下，Index 是如何使用两种算法来实现字符串查找的：
我们把整体的函数分为 三个部分 ：
子串 子串
2 和 3 两种情况的区分是因为要根据这个信息来更快的选择适合的算法，如下：
// Index returns the index of the first instance of substr in s, or -1 if substr is not present in s.
func Index(s, substr string) int {
n := len(substr)
switch {
// ========= 第一部分 ===========
// 处理简单的情况，
// 当子串是 0 的时候，直接认为 index 为 0；
// 当子串是 1 的时候，使用 IndexBytes，也就是一个字符一个字符找，相当于遍历；底层使用 IndexByteString；
// 当子串的长度大于主串，则不可能找到，返回 -1；
case n == 0:
return 0
case n == 1:
return IndexByte(s, substr[0])
case n == len(s):
if substr == s {
return 0
}
return -1
case n > len(s):
return -1
// ========= 第二部分 ===========
// 处理子串的长度小等于最大长度 MaxLen 的时候；
// MaxLen 是一个可变的数值，根据不同的CPU平台有不同的值；
case n <= bytealg.MaxLen:
// 当主串小于 MaxBruteForce 的值时，则直接使用 BF 算法；
// MaxBruteForce 也是一个可变数值，根据不同的平台有不同的值，在64位机器上是 64
if len(s) <= bytealg.MaxBruteForce {
// 这个函数在部分平台有汇编完成的优化版本，比如 amd64；
// 其他平台则是和 《第三部分》 一样；
return bytealg.IndexString(s, substr)
}
// c0 和 c1 是模式串的第0个和第一个字符
c0 := substr[0]
c1 := substr[1]
// i 和 t 是循环的 起始和终止条件，
// 相当于算法中的，从 0 开始，遍历 n-m+1 次；
i := 0
t := len(s) - n + 1
// 查找失败的次数
fails := 0
// 开始查找
for i < t {
if s[i] != c0 { // 模式串第0个字符不等于 s[i]
// 为了避免一开始就出现失败次数太多，而进入到 IndexString 中，要尽可能使用 IndexByte
// 做更多的事情。
// 因为 IndexByte 要比 IndexString 快得多。
// 使用 IndexByte 继续向后查找 主串中，和模式串 第0个字符相等的位置
o := IndexByte(s[i+1:t], c0)
if o < 0 { // 如果没有找到，那么，不可能找到子串了；
return -1
}
i += o + 1 // 从找到的地方，继续后面的工作
}
if s[i+1] == c1 && s[i:i+n] == substr {
// 判断模式串第1个字符时候和 主串下一个字符相等
// 如果相等，那么判断整个字符串是否相等
// 如果相等，那么找到了
return i
}
// 失败次数 +1
// 主串索引 +1
fails++
i++
// 如果失败次数太多，则直接切换到 IndexString 中（汇编 或者 第三部分的处理）
if fails > bytealg.Cutover(i) {
r := bytealg.IndexString(s[i:], substr)
if r >= 0 {
return r + i
}
return -1
}
}
return -1
}
// =========== 第三部分 =============
// 这一部分首先使用和第二部分上半边一样的方式来处理；
// 当失败次数达到一定程度，则切换到 RK 算法上；
c0 := substr[0]
c1 := substr[1]
i := 0
t := len(s) - n + 1
fails := 0
for i < t {
if s[i] != c0 {
o := IndexByte(s[i+1:t], c0)
if o < 0 {
return -1
}
i += o + 1
}
if s[i+1] == c1 && s[i:i+n] == substr {
return i
}
i++
fails++
// ==== 以上，和 第二部分相同 ========
// 如果查找没有结束
// 且 失败数 >= (索引位置 + 4) / 16，则使用 RK 算法；
if fails >= 4+i>>4 && i < t {
// 使用 RK 算法开始查找
j := bytealg.IndexRabinKarp(s[i:], substr)
if j < 0 {
return -1
}
return i + j
}
}
return -1
}
BF算法RK算法func IndexRabinKarp(s, substr string) int {
// 使用哈希算法计算出了模式串的哈希值，
// 还有 最高位+1 的进位乘数 （ 为什么 +1，后面解释）
hashss, pow := HashStr(substr)
n := len(substr)
var h uint32
// 使用循环计算主串中，第0位开始的主串的哈希值
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]) // 减去最高位的字符
// 为什么 pow 是 最高位+1 的进位乘数呢？
// 因为我们在第一步，先对整体的数值进行了进位，所以
// 最高位就变成了 最高位+1
// 此时，主串的哈希值已经计算完毕
i++ // 向后推进
// 比对哈希值
// 如果相同则对比子串内容
if h == hashss && s[i-n:i] == substr {
return i - n
}
}
return -1
}
// 如何计算字符串的哈希，
// 返回了 哈希值 和 乘法因子
func HashStr(sep string) (uint32, uint32) {
hash := uint32(0)
// PrimePK 相当于我们算法中讲到的 进制值，在这里是 16777619，
// 相当于 16777619进制。
// 这里一次计算每一个字符的 uint32位值，然后乘以进制值进位。
for i := 0; i < len(sep); i++ {
hash = hash*PrimeRK + uint32(sep[i])
}
// 这里开始计算 最高位 +1 的乘法因子
// pow 为最终的乘数因子，sq 为进位值
//
// 这里可以直接对子串进行循环，然后计算出 pow 值，
// 但相对于下面的算法，效率会低很多；
var pow, sq uint32 = 1, PrimeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 { // 最低位 是 1，则使用 pow 乘以 sq
pow *= sq
}
sq *= sq // 最低位是 0，则将进位值向前进位
}
return hash, pow
}
结尾
Brute ForceRabin-KarpRabin-Karp