Golang strings中的Index函数(字符串查找)

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1. 前言

在Golang中strings模块Index原型如下
func Index(s, substr string) int

Golang中 substr长度大于64/32(视CPU的情况而定)的情况，
查找采用的rabin-karp算法，它是由Richard M. Karp和 Michael O. Rabin在1987年提出的。（1987年就这么牛了，还让人活不活）

该算法的实际应用是检测抄袭

2. 点评

假定s长度为n, substr长度为m
它的时间复杂度为O(n + m)，最坏情况下的时间复杂度为O(n * m)。
KMP算法的时间复杂度也是O(n + m), 可见它的速度并不慢
它的相比于KMP算法的最大优势是，实现简单，易于理解

2.1 以下是暴力算法的伪码

function NaiveSearch(string s[1..n], string pattern[1..m])
   for i from 1 to n-m+1
      for j from 1 to m
         if s[i+j-1] ≠ pattern[j]
            jump to next iteration of outer loop
      return i
   return not found

2.2 以下是rabin-karp算法的伪码

function RabinKarp(string s[1..n], string pattern[1..m])
  hpattern := hash(pattern[1..m]);
  for i from 1 to n-m+1
    hs := hash(s[i..i+m-1])
    if hs = hpattern
      if s[i..i+m-1] = pattern[1..m]
        return i
  return not found

大家可以看出rabin-karp算法其实是暴力算法的改进版，
简单的说:
就是先匹配Pattern的哈希值，如果hash值相同，才实际进行字符串匹配(line 4/5/6)

2.3 Hash函数

由于hash函数需要调用n-m+1次，如何找到低成本的Hash函数就至关重要。rabin-karp算法利用rolling hash的特性，降低了计算成本(函数的时间复杂度为O(1))。

我们可以构造一个最简单的rolling hash，简单的将字符串中的每个字符的ASCII码值相加，比如

func SimpleRollingHash(s string) int {
    total := 0
    for i := 0; i < len(s); i++ {
        total += int(s[i])
    }
    return total
}

可以推出

SimpleRollingHash(s[i+1:i+m]) = SimpleRollingHash(s[i:i+m-1]) - int(s[i]) + int(s[i+m])

当然SimpleRollingHash的冲突概率会很高，不过其它rolling hash函数与它非常类似，这里列出是为了便于大家理解。
更多实现细节请移步参考文献1。

3. Golang 1.10 中相关源码

.//strings/strings.go

// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619

// hashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
// hashStr也是也是1种rolling hash
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
        }
        sq *= sq
    }
    return hash, pow
}

func indexRabinKarp(s, substr string) int {
    // Rabin-Karp search
    hashss, pow := hashStr(substr)
    n := len(substr)
    var h uint32
    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])
        i++
        // 重要的代码
        // 如果hash函数选用不当，可能导致哈希值频繁冲突
        // 时间复杂度退化为O(n * m)
        if h == hashss && s[i-n:i] == substr {
            return i - n
        }
    }
    return -1

}

参考资料

Rabin–Karp algorithms

请我喝瓶饮料

微信支付码

vearne@ut

260