Contents

# 28. Implement strStr()

## 題目 :

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

### Example :

Note

Input: haystack = “hello”, needle = “ll”

Output: 2

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

Input: haystack = “”, needle = ""

Output: 0

#### 解題思路 :

• 這題其實如果要得到線性的時間複雜度的話需要使用KMP Algorithm，並沒有很簡單
• KMP主要在尋找子字串時使用，他的核心概念就是他會需要生成一個next table

• 那第二個重點就是如何製作next table ?

### 以下是我的解法 - time complexity: O(n+m) , space complexity: O(n)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 `````` `````` func strStr(haystack string, needle string) int { n := len(needle) if n == 0 { return 0 } next := make([]int, len(needle)) getNext(next, needle) j := 0 for i := 0; i < len(haystack); i++ { for j > 0 && haystack[i] != needle[j] { j = next[j-1] } if haystack[i] == needle[j] { j++ } if j == n { return i - n + 1 } } return -1 } func getNext(next []int, s string) { j := 0 for i := 1; i < len(s); i++ { for j > 0 && s[i] != s[j] { j = next[j-1] } if s[i] == s[j] { j++ } next[i] = j } } ``````