Sunday Search 算法实现

Sunday Search 是什么

Sunday算法由Daniel M.Sunday在1990年提出，是一种字符串模式匹配算法，能够以O(n)的时间复杂度下完成子串索引。

Sunday Search 的原理

• Sunday算法从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
• 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
• 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

Sunday Search 的实现

本文中我们使用Go语言实现该算法

func SundaySearch(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}

	if len(haystack) == 0 && len(needle) != 0 {
		return -1
	}

	sIndex := 0
	pIndex := 0
	space := 0

	keys := make([]int, 256)//记录每个字符出现的最右侧位置

	for i := 0; i < 256; i++ {
		keys[i] = -1
	}

	for i := 0; i < len(needle); i++ {
		keys[needle[i]] = i
	}

	for sIndex < len(haystack) {
		if haystack[sIndex] == needle[pIndex] {
			sIndex++
			pIndex++
			if pIndex == len(needle) {
				return sIndex - pIndex
			}
		} else {
			pIndex = 0
			if space+len(needle) < len(haystack) {
				space += len(needle) - keys[haystack[space+len(needle)]]//寻找下个模式串匹配的初始位置
			} else {//位移与模式串的长度和超出原字符串的长度
				return -1
			}
			sIndex = space
		}
	}

	return -1
}

参考文献

https://blog.csdn.net/v_JULY_v/article/details/7041827