Contain()
func Contains(s, substr string) bool
Contains()返回一个布尔值，若substr存在于s中，则返回true，不存在则返回false。golang
// Contains reports whether substr is within s
func Contains(s, substr string) bool {
return Index(s, substr) >= 0
}
Index()
咱们再来看Index(),
func Index(s, substr string) int
Index()返回substr出如今原始string s 中的 位置，若是s中meiyousubstr，则返回-1算法
// 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) //先获取substr的长度 赋给n
switch {
case n == 0: //若是 substr的长度为0 ，则返回0，
return 0
case n == 1:
return IndexByte(s, substr[0]) // 后面再看一下IndexByte()的源码
case n == len(s): // 若是 s和substr长度相等，直接判断俩字符串是否如出一辙
if substr == s {
return 0
}
return -1
case n > len(s): // 若是 substr的长度大于s的长度，那确定不存在了，返回-1，说明substr不存在于s中
return -1
case n <= bytealg.MaxLen: // 后面得看bytealg.MaxLen
// Use brute force when s and substr both are small
if len(s) <= bytealg.MaxBruteForce { // const型 ：const MaxBruteForce = 64
return bytealg.IndexString(s, substr)
}
c0 := substr[0]
c1 := substr[1]
i := 0
t := len(s) - n + 1
fails := 0
for i < t {
if s[i] != c0 {
// IndexByte is faster than bytealg.IndexString, so use it as long as
// we're not getting lots of false positives.
o := IndexByte(s[i:t], c0)
if o < 0 {
return -1
}
i += o
}
if s[i+1] == c1 && s[i:i+n] == substr {
return i
}
fails++
i++
// Switch to bytealg.IndexString when IndexByte produces too many false positives.
if fails > bytealg.Cutover(i) {
r := bytealg.IndexString(s[i:], substr)
if r >= 0 {
return r + i
}
return -1
}
}
return -1
}
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:t], c0)
if o < 0 {
return -1
}
i += o
}
if s[i+1] == c1 && s[i:i+n] == substr {
return i
}
i++
fails++
if fails >= 4+i>>4 && i < t {
// See comment in ../bytes/bytes_generic.go.
j := indexRabinKarp(s[i:], substr)
if j < 0 {
return -1
}
return i + j
}
}
return -1
}
internel/bytealg中：
MaxLen is the maximum length of the string to be searched for (argument b) in Index.app
main.go:5:2: use of internal package internal/bytealg not allowed
想看一下bytealg.Maxlen等于多少，可是go build 后报错，说internal/bytealg不容许用函数
在internel包搜了一下MaxLen
ui
如是，MaxLen于CPU有关。spa
package bytealg
import "internal/cpu"
const MaxBruteForce = 64
func init() {
if cpu.X86.HasAVX2 {
MaxLen = 63
} else {
MaxLen = 31
}
}
cpu.X86.HasAVS2是个啥？来看一下cpu.X86.HasAVX2code
X86.HasAVX = isSet(ecx1, cpuid_AVX) && osSupportsAV
看一下isSet()图片
func isSet(hwc uint32, value uint32) bool {
return hwc&value != 0
}
// cpuid is implemented in cpu_x86.s. func cpuid(eaxArg, ecxArg uint32) (eax, ebx, ecx, edx uint32)
_, _, ecx1, edx1 := cpuid(1, 0)
osSupportsAVX := false
// For XGETBV, OSXSAVE bit is required and sufficient.
if X86.HasOSXSAVE {
eax, _ := xgetbv()
// Check if XMM and YMM registers have OS support.
osSupportsAVX = isSet(eax, 1<<1) && isSet(eax, 1<<2)
}
。。。 涉及cpu硬件相关的了。。。。ip
回到strings.Index(),go on
虽然bytealg.MaxLen不知道是多少，可是可是从case语句不难看出，bytealg.MaxLen是一个可能要比substr的长度小的值，若是substr的确比bytealg.MaxLen小，则执行case n <= bytealg.MaxLen ，不然跳出case。
直接看case 几种状况都不知足的块ci
c0 := substr[0] // 获取substr的第一个字符
c1 := substr[1] // 第二个
i := 0
t := len(s) - n + 1 // t是s的长度减substr的长度 + 1 ，，，啧啧啧
fails := 0
for i < t { // 进入循环
if s[i] != c0 { // 若是substr的头 不等于 s[i]
o := IndexByte(s[i:t], c0) // 直接将substr的头放在s的slice中判断
if o < 0 { // 不存在，直接返回-1
return -1
}
// substr的头存在于 s[i]剩下的部分 。那直接看substr的第二个字符存不存在于 s[i+o]中，
i += o
}
if s[i+1] == c1 && s[i:i+n] == substr { // 恩，若是substr的头等于s[i] 直接看substr的第二个字符等不等于s[i+1]
// 而且判断s的slices[i:i+n]和substr相等不，若是相等，那么substr就存在于s中了，位置是 i
return i
}
// 其余状况，i++ ，在for的断定条件下继续循环。失败次数+1，
i++
fails++
if fails >= 4+i>>4 && i < t { 若是失败次数大于等于 4+i 获得二进制数右移四位而且i < t ，
// 得看一下indexrabinKarp 是个啥？
//不难看出，这块是针对于失败次数比较多的时候执行的。
// See comment in ../bytes/bytes_generic.go.
j := indexRabinKarp(s[i:], substr)
if j < 0 {
return -1
}
return i + j
}
}
// 若是循环执行完了，到这儿了，说明substr不存在于s中，返回-1
return -1
indexRabinKarp()
看一下indexRabinKarp() 吧！
Rabin-Karp是个啥？查了一下。
原来rabinkarp是一种字符串查找算法，看看吧！想必你已经知道Rabin-Karp了，直接跳到下一个目录吧。
Rabin-Karp Algorithm-WikiPedia
func indexRabinKarp(s, substr string) int {
// Rabin-Karp search
hashss, pow := hashStr(substr) // hashStr是个啥？
n := len(substr)
var h uint32
for i := 0; i < n; i++ { // 当 0 < i < n 时 循环，获得h，执行下一块的if判断
h = h*primeRK + uint32(s[i])
}
if h == hashss && s[:n] == substr {
// 若是 判断substr是否是就是紧挨这s的头对齐的时候而且相等的，若是是，index = 0，返回0
return 0
}
for i := n; i < len(s); { // 若是 substr和s的头对齐以后不相等，则继续循环， 判断下。从i = n开始判断
h *= primeRK
h += uint32(s[i])
h -= pow * uint32(s[i-n])
i++
if h == hashss && s[i-n:i] == substr {
return i - n
}
}
return -1
}
hashStr
hashStr()
// 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.
func hashStr(sep string) (uint32, uint32) {
hash := uint32(0)
for i := 0; i < len(sep); i++ {
hash = hash*primeRK + uint32(sep[i]) // hash 是循环len(sep)次的 这串操做的int32型的数
//假设len(sep) = 4
//i = 0: hash = uint32(sep[0])
//i = 1: hash = uint32(sep[0])* primeRK + uint32(sep[1])
//...
}
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 { i是seq的长度，执行一次循环体以后，i = i + i右移一位(二进制)，
// 等于 i = i + floor(i/2) （十进制，）
if i&1 != 0 {
pow *= sq // 若是i就是1 了 pow = pow * sq
}
sq *= sq // i不是1，sq = sq*sq
}
// 假设len(sep) = 4
// i = 4, sq = sq^2
// i = 2, sq = sq^4
// i = 1, pow = pow*sq = sq = sq^4
// 假设 len(sep) = 5
// i = 5, sq = sq^2 ，5的二进制101 >> 1 = 10
// i = 2, sq = sq^4
// i = 1, pow = sq = sq^4 ，仍是sq^len(sep)
return hash, pow 输入一个字符串，返回俩uint值
}
Rabin-Karp算法就是 为了不挨个字符对文本s和substr进行比较，能够尝试一次性判断二者是否相等。所以，咱们须要一个好的哈希函数（hash function）。经过哈希函数，能够算出代匹配字符串substr的哈希值，而后将它和文本中的s的切片s[x：y]的哈希值进行比较。
好比原字符串为： AABAACAADAABAABA
个人substr为：AABA先算出AABA 的hash，而后按照substr的长度算AABA的hash，比一下,结果俩hash相等，那么再把原字符串比一下，还相等，获得一个index0继续，再算ABAA的hash比一下，不相等，继续，再算BAAC的hash比一下，不相等，继续，再算AACA的hash比一下，不相等，就这样，若是目标字符串和原字符串的hash比的结果一致，还得再把目标字符串和原字符串的字符串值比一下，由于很差的hash函数可能会有hash冲突。