Contents

[Golang][Leetcode][String]刷題系列-28-KMP Algorithm


28. Implement strStr()


Level : Easy

原題連結 : Click

題目 :

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呢? 假設一個情境當你有一個字串ABBCABBCDEABBCF,需要你找出ABBCF字串的位置,當你從頭一個一個比對時,會在第5個字符出現不一樣,AF 這時候就要去next table的第五個也就是index = 4 的位置看從哪裡開始重新比對才有效率,這時候next table會再index = 4的的值會是 0,也就是再跟你說你需要從index = 0的地方重新尋找,這時候你需要重新回到ABBCF的開頭A去比對ABBCABBCDEABBCF中的第5格字符A,然後以次類推繼續尋找,當只要碰壁就去請教next table,你該從哪裡重新開始檢查。

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

其實只需要用two pointers就可以找到next table,這邊要提醒一下,next table的寫法有很多種,我這邊只展示將當前element 的 next value都填在上一個element的位置,也就是說假設一個子字串ABCABF的next table會像是000120,當F碰壁時,就會去找到F的上一個value也就是2,也就是說他會告訴你該去index = 2 的地方也就是C重新開始檢查,以此類推…


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

為何能做到O(n+m)呢? 因為他只是在主程式部分時將主字串traversal一遍與製作next table時將子字串traversal一遍 Runtime: 0 ms, faster than 100.00% of Go online submissions for Implement strStr().


 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
    }
    

}


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!