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

    // 生成next数组
    next := make([]int, len(needle))
    i, j := 1, 0
    // 起始位置初始化为0
    next[0] = 0
    // 遍历needle字符串，生成i下标对应的回溯位置
    for ; i < len(needle); i++ {
        // 当下标i与下标j的元素值不匹配时，通过next数组回溯
        for j > 0 && needle[i] != needle[j] {
            j = next[j-1]
        }

        // 如果此时下标i与下标j的元素值可以匹配上，生成i下标对应的回溯位置(j+1)
        // 此处填入j+1表示，匹配时当匹配串与原串存在差异，匹配串可以从j+1处重新开始匹配(因为匹配串从0到j都可以认为默认匹配原串)，而原串无须移动下标
        if needle[i] == needle[j] {
            next[i] = j + 1
            // 匹配成功，j右移一位
            j++
        } else {
            // 反之表示没有相同前缀的子串，填入0
            next[i] = 0
        }
    }

    // 开始匹配逻辑
    i, j = 0, 0
    for ; i < len(haystack); i++ {
        // 当下标i与下标j的元素值不匹配时，通过next数组回溯
        for j > 0 && haystack[i] != needle[j] {
            j = next[j-1]
        }
        if haystack[i] == needle[j] {
            j++
        }

        // 当匹配到最后一个字符也成功时，返回下标
        if j == len(needle) {
            return i - j + 1
        }
    }

    return -1
}