LeetCode 28 实现strStr()

题目：

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

解题：

字符串逐个匹配，不相等的就跳过

代码：

func strStr(haystack string, needle string) int {
    pos := -1
    h, n := len(haystack), len(needle)
    if n == 0 || n > h {
        return pos
    }
    for i := 0; i < h-n+1; i++ {
        if haystack[i] == needle[0] {
            flag := true
            for j := 0; j < n; j++ {
                if haystack[i+j] != needle[j] {
                    flag = false
                    break
                }
            }
            if flag {
                return i
            }
        }
    }
    return pos
}

官方解答：

// 暴力匹配
func strStr(haystack, needle string) int {
    n, m := len(haystack), len(needle)
outer:
    for i := 0; i+m <= n; i++ {
        for j := range needle {
            if haystack[i+j] != needle[j] {
                continue outer
            }
        }
        return i
    }
    return -1
}
// Knuth-Morris-Pratt 算法
func strStr(haystack, needle string) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }
    pi := make([]int, m)
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && needle[i] != needle[j] {
            j = pi[j-1]
        }
        if needle[i] == needle[j] {
            j++
        }
        pi[i] = j
    }
    for i, j := 0, 0; i < n; i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = pi[j-1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1
}