Skip to content

Instantly share code, notes, and snippets.

@MOOOWOOO
Created June 27, 2022 02:47
Embed
What would you like to do?
search subslice in slice
package main
// search all sub slices
func SearchSubSlice(mainSlice, subSlice []byte) []int {
var result []int
result = nil
// 主切片为空,直接返回 nil
// if main slice is nil or empty, just return nil
if mainSlice == nil {
return result
}
mainSliceLen := len(mainSlice)
if mainSliceLen == 0 {
return result
}
// 子切片为空,直接返回 nil
// if sub slice is nil or empty, just return nil
if subSlice == nil {
return result
}
subSliceLen := len(subSlice)
if subSliceLen == 0 {
return result
}
// 主切片比子切片还短,直接返回 nil
// if main slice is shorter than sub slice, just return nil
if mainSliceLen < subSliceLen {
return result
}
// 查找到子切片后,设置子切片在主切片中起始的偏移量
// index offset of first element of sub slice in main slice when sub slice is found in main slice
indexOffset := subSliceLen - 1
// 子切片的位移游标
// sub slice seek
subSliceSeek := 0
// 匹配的次数,最大为子切片长度几表明成功匹配上
// total match times check point, max value is length of sub slice which means match success
checkPoint := 0
// 循环主切片,查找子切片
// loop main slice
for index, value := range mainSlice {
if value == subSlice[subSliceSeek] {
// 每当匹配上一个元素
// once an element matches
// 子切片的位移游标后移一位
// sub slice seek move forward
subSliceSeek++
// 匹配的个数增加一
// check point ++
checkPoint++
} else {
// 一旦有一个元素不匹配,则直接重置子切片的位移游标和匹配个数
// once an element mismatches, reset sub slice seek & check point
subSliceSeek = 0
checkPoint = 0
// 这里重置后,必须在将当前元素与子切片首位元素比较一次,避免出现 [a,b] [a,a,b] 场景中被漏掉的情况
// after reset, retry to match first element of sub slice
// in case of missed [a,b] [a,a,b]
if value == subSlice[subSliceSeek] {
subSliceSeek++
checkPoint++
}
}
// 当匹配成功时,将本次匹配中,主切片的起始位置存入结果切片(result)中,然后直接重置子切片的位移游标和匹配个数,等待下一轮匹配
// once all elements in sub slice matches, store the first element index into result slice.
if checkPoint == subSliceLen {
result = append(result, index - indexOffset)
subSliceSeek = 0
checkPoint = 0
}
}
return result
}
// search first N times sub slices
func SearchSubSliceN(mainSlice, subSlice []byte, N int) []int {
var result []int
result = nil
// 主切片为空,直接返回 nil
// if main slice is nil or empty, just return nil
if mainSlice == nil {
return result
}
mainSliceLen := len(mainSlice)
if mainSliceLen == 0 {
return result
}
// 子切片为空,直接返回 nil
// if sub slice is nil or empty, just return nil
if subSlice == nil {
return result
}
subSliceLen := len(subSlice)
if subSliceLen == 0 {
return result
}
// 主切片比子切片还短,直接返回 nil
// if main slice is shorter than sub slice, just return nil
if mainSliceLen < subSliceLen {
return result
}
// 查找到子切片后,设置子切片在主切片中起始的偏移量
// index offset of first element of sub slice in main slice when sub slice is found in main slice
indexOffset := subSliceLen - 1
// 子切片的位移游标
// sub slice seek
subSliceSeek := 0
// 匹配的次数,最大为子切片长度几表明成功匹配上
// total match times check point, max value is length of sub slice which means match success
checkPoint := 0
// result length
resultLen := 0
// 循环主切片,查找子切片
// loop main slice
for index, value := range mainSlice {
if value == subSlice[subSliceSeek] {
// 每当匹配上一个元素
// once an element matches
// 子切片的位移游标后移一位
// sub slice seek move forward
subSliceSeek++
// 匹配的个数增加一
// check point ++
checkPoint++
} else {
// 一旦有一个元素不匹配,则直接重置子切片的位移游标和匹配个数
// once an element mismatches, reset sub slice seek & check point
subSliceSeek = 0
checkPoint = 0
// 这里重置后,必须在将当前元素与子切片首位元素比较一次,避免出现 [a,b] [a,a,b] 场景中被漏掉的情况
// after reset, retry to match first element of sub slice
// in case of missed [a,b] [a,a,b]
if value == subSlice[subSliceSeek] {
subSliceSeek++
checkPoint++
}
}
// 当匹配成功时,将本次匹配中,主切片的起始位置存入结果切片(result)中,然后直接重置子切片的位移游标和匹配个数,等待下一轮匹配
// once all elements in sub slice matches, store the first element index into result slice.
if checkPoint == subSliceLen {
result = append(result, index - indexOffset)
resultLen++
subSliceSeek = 0
checkPoint = 0
}
// 如果已匹配的数量达到 N,则直接跳出循环
// if result element is up to preset N times break the loop
if N == resultLen {
break
}
}
return result
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment