Created
June 27, 2022 02:47
search subslice in slice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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