golang关于查找字符串的源码

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

参考