/**
 * @param source: 
 * @param target: 
 * @return: return the index
 */
func StrStr(haystack string, needle string) int {
	// 在剩余长度不足时直接退出，是否加1可以代特殊值
	for i := 0; i < len(haystack)-len(needle)+1; i++ {
		equal := true
		// 写 for 循环比较，不需要额外空间
		for j := 0; j < len(needle); j++ {
			if haystack[i+j] != needle[j] {
				equal = false
				break
			}
		}
		if equal {
			return i
		}
	}
	return -1
}

func StrStr2(haystack string, needle string) int {
	// 如果 needle 是空字符串，返回0
	if len(needle) == 0 {
		return 0
	}

	// 如果 haystack 的长度小于 needle 的长度，返回-1
	if len(haystack) < len(needle) {
		return -1
	}

	// 定义哈希相关的常量
	const base = 256
	const mod = 101 // 选择一个合适的质数作为模数

	// 计算 needle 的哈希值
	needleHash := 0
	haystackHash := 0
	h := 1

    // 为了防止乘出来的数太大，边乘边模
	for i := 0; i < len(needle)-1; i++ {
		h = (h * base) % mod
	}

	for i := 0; i < len(needle); i++ {
		needleHash = (base*needleHash + int(needle[i])) % mod
		haystackHash = (base*haystackHash + int(haystack[i])) % mod
	}

	// 滑动窗口进行匹配
	for i := 0; i <= len(haystack)-len(needle); i++ {
		// 如果哈希值相同，进一步检查实际的字符串
		if needleHash == haystackHash {
			match := true
			for j := 0; j < len(needle); j++ {
				if haystack[i+j] != needle[j] {
					match = false
					break
				}
			}
			if match {
				return i
			}
		}

		// 计算下一个窗口的哈希值
		if i < len(haystack)-len(needle) {
			haystackHash = (base*(haystackHash-int(haystack[i])*h) + int(haystack[i+len(needle)])) % mod
			if haystackHash < 0 {
				haystackHash += mod
			}
		}
	}

	return -1
}