主要介绍strings包中的 strings.go/search.go/replace.go

 

string.go中主要介绍Index函数，该函数寻找s中第一次出现substr的位置，返回position或-1:

基本代码如下：

1 func Index(s, substr string) int {  2     n := len(substr)  3     switch {  4    　　...  5     case n <= bytealg.MaxLen:  6         // Use brute force when s and substr both are small  7         if len(s) <= bytealg.MaxBruteForce {  8             return bytealg.IndexString(s, substr)  9         } 10         c := substr[0] 11         i := 0 12         t := s[:len(s)-n+1] 13         fails := 0 14         for i < len(t) { 15             if t[i] != c { 16                 // IndexByte is faster than bytealg.IndexString, so use it as long as 17                 // we're not getting lots of false positives. 18                 o := IndexByte(t[i:], c) 19                 if o < 0 { 20                     return -1 21                 } 22                 i += o 23             } 24             if s[i:i+n] == substr { 25                 return i 26             } 27             fails++ 28             i++ 29             // Switch to bytealg.IndexString when IndexByte produces too many false positives. 30             if fails > bytealg.Cutover(i) { 31                 r := bytealg.IndexString(s[i:], substr) 32                 if r >= 0 { 33                     return r + i 34                 } 35                 return -1 36             } 37         } 38         return -1 39     } 40     c := substr[0] 41     i := 0 42     t := s[:len(s)-n+1] 43     fails := 0 44     for i < len(t) { 45         if t[i] != c { 46             o := IndexByte(t[i:], c) 47             if o < 0 { 48                 return -1 49             } 50             i += o 51         } 52         if s[i:i+n] == substr { 53             return i 54         } 55         i++ 56         fails++ 57         if fails >= 4+i>>4 && i < len(t) { 58             // See comment in ../bytes/bytes_generic.go. 59             j := indexRabinKarp(s[i:], substr) 60             if j < 0 { 61                 return -1 62             } 63             return i + j 64         } 65     } 66     return -1 67 } 68  69  70 func indexRabinKarp(s, substr string) int { 71     // Rabin-Karp search 72     hashss, pow := hashStr(substr) 73     n := len(substr) 74     var h uint32 75     for i := 0; i < n; i++ { 76         h = h*primeRK + uint32(s[i]) 77     } 78     if h == hashss && s[:n] == substr { 79         return 0 80     } 81     for i := n; i < len(s); { 82         h *= primeRK 83         h += uint32(s[i]) 84         h -= pow * uint32(s[i-n]) 85         i++ 86         if h == hashss && s[i-n:i] == substr { 87             return i - n 88         } 89     } 90     return -1 91  92 } 93  94 func hashStr(sep string) (uint32, uint32) { 95    hash := uint32(0) 96    for i := 0; i < len(sep); i++ { 97       hash = hash*primeRK + uint32(sep[i]) 98    } 99    var pow, sq uint32 = 1, primeRK100    for i := len(sep); i > 0; i >>= 1 {101       if i&1 != 0 {102          pow *= sq103       }104       sq *= sq105    }106    return hash, pow107 }

　　可以看到在substr较短的情况下使用了暴力匹配，否则使用rabin-karp算法进行比较，以下对rabin-karp以及golang的实现方式进行简要总结：

1. Rabin-Karp算法类似于暴力匹配，假设A为s中即将于substr进行比较的字符串，传统方法需要将A中所有的字符与substr一一比较来判断两者是否相等，这太耗时了；

2. 为此我们将上述比较替换成比较A与substr的hash值，这样就将字符串匹配简化为整形的判等。为了减小运算量，这里希望对于一个长字符串的hash值能够尽可能短，但实际上不能指望长字符串有短hash值，而且当这个值很大的时候可能溢出， 这个时候就需要用求余来解决。

3. hash以及hash求余都会有hash值碰撞的问题，所以最后要把hash值相等的两个串再逐个匹配一下确认其相等。golang在实现上实际上使用了uint32大小的限制，隐式地取了余数。

4. 这里值得一提的是golang在hash方法的选择上是很特殊的。它使用了一个特殊的hash函数（s[0]*pow(PrimeRK,n-1)+s[1]*pow(PrimeRK,n-2)+...+s[n-1]），使得 hash[i+1:i+n+1] = hash[i:i+n]*PrimeRK+s[i+n+1]-s[i]*pow(PrimeRK,n) 也就是说存在hash[i+1:i+n+1]=f(hash[i:i+n]) 的关系，即A的下一个待匹配项能够迅速由A计算得到，大大加快了计算hash[i+1:i+n+1]的速度。

 

===未完待续======