字符串查

两种算法
查找字符串有两种相对成熟又实现简单的算法，一个叫做 Brute Force ，叫做暴力匹配，或者朴素匹配的算法；另一个叫做 Rabin-Karp，是前者的升级版，加入了 哈希算法来提高效率，要稍微复杂一点。
在 Golang 的字符串查找中，两种算法都有用到。这和这两种算法在不同的场景下的优势不同有很大关系。我们可以先来看一下这两种算法的原理是什么，然后再对照到 Golang 的源码中。

Brute Force
这种算法其实就是最简单的一个个的字符去做对比来判断字符串是否一样。这种算法的特点就是实现简单，但是相应的效率也不是很高。
假设我们有两个字符串，A串 和 B串。如果我们要在 A 中查找 B，那么，我们把 A 叫做 主串，我们 B 串叫做 模式串 。A 的长度为 n，B的长度为 m，那么就有 n>=mn >= mn>=m。
如果，我们要在 A 中查找B，那么我们就需要从 编号为 0 开始的地方，一直到 n-m 的地方，将 m 长度的子串和 B 对比，看看是否相同。那么，也就是要对比 n−m+1n-m+1n−m+1 次，每次对比 m 个字符，换算成公式就是：(n−m+1)∗m(n-m+1)m(n−m+1)∗m ，所以，这个算法的时间复杂度就是 O(n∗m)O(nm)O(n∗m) 。

这样的时间复杂度实在不是一个高效的实现，但实际中还是有很多地方使用这种算法（比如 Golang），究其原因就是因为两个：一是简单的算法实现容易，也比较容易理解，有问题方便排查；二是实际情况中，会出现这么性能差的时候从概率上是比较小的。
假设我们有一个字符串是 “xxxxxxxx…….xxxxx” ，我们要在这个主串中，查找模式串 “xxxxxxy”，在这种情况下，算法就会退化到最差的时间复杂度上面。但实际上这种情况会非常少。
Rabin-Karp
那么如果真的出现了上面的算法的最坏情况，怎么办呢？我们就可以使用这种加强版的算法来避免 BF 算法退化到最差的情况。
这个算法其实就是 BF 算法的哈希版。我们先设计一个哈希函数，用它将 模式串 的哈希值计算出来，然后再用它计算出主串中 从0开始的 m 长度的子串的哈希值，对比两个哈希值。如果不是的话，那么计算从1开始 m 长度的子串哈希值，……一直到 n-m个。如下图所示：

那么，如果要用哈希算法的话，就会遇到几个问题：

如何解决哈希冲突的问题？
主串中的每一个子串都需要计算哈希值，效率如何提高？

问题一：如何解决哈希冲突的问题
哈希冲突是一定会出现的情况，解决的方法在这个算法里非常简单，直接再对比一下字符串本身就可以了。如果哈希不匹配，就不需要对比字符串本身。
问题二：如何解决计算哈希效率的问题
这个问题需要哈希计算的函数实现非常有技巧才行。
我们假设要匹配的字符串的字符集中只包含 X 个字符，我们可以用一个 X 进制数来表示一个子串，尝试将一个字符串的每一个字符计算一个基础的哈希值，然后再乘以所在的位置，最后将所有的值加起来，最后将这个 X 进制数转化成十进制数，作为子串的哈希值。
为了问题可以更简单的描述，我们假设我们的字符串中只有26个英文字母，就用26进制来表示一个字符串，所以 X=26X=26X=26。从 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
复制代码
可以看到 模式串 和 主串的位置0开始的子串，哈希值是明显不同的，这样就可以不需要比对字符串内容了，直接比对下一个子串。
那么，如何解决效率问题呢？
我们可以看到，当我们比对下一个子串的时候，中间的三个黄色箭头的字母哈希值是不需要重新计算的。我们只需要去掉最高位的哈希值，加上新的最低位即可。 又因为，最高位的进制乘数是确定的 26 * 26 * 26 ，而最低位是不需要进位的，所以就是字母对应的本身的值。所以，我们只需要记录下来，最高位的进制乘数即可。这样就不需要每次重复计算哈希值了。
比如上面的例子中。计算位置1开始的子串只需要使用：
Hash(“hisi”) = (338902 - 192626*26) *26 + 8 * 1 = 128916
复制代码
这样，计算哈希就会非常高效。
Golang 中的字符串查找
Golang 中的字符串查找在 strings 包中，有多个函数，我们以 strings.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
}
复制代码
结尾
至此，Golang 标准库对于 Brute Force 和 Rabin-Karp 两种算法的使用详解已经介绍完了。如果了解了算法的原理，那么就可以非常容易的明白，具体的实现是怎么做的。
Golang 中的 Rabin-Karp 的哈希计算非常有意思，而且很精炼。希望学到这种方法可以用到我们日常的开发中。

https://juejin.im/post/6876260518105972749

对照可以复习下kmp算法，kmp算法对模式串中有重复前缀的匹配效率提高较大
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html