search subslice in slice

search_subslice.go

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
}