Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://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

}

参考资料

  1. Rabin–Karp algorithms

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据