KMP algorithm in golang


  • 0
    G
    func buildKmp(n string) []int{
        table := make([]int,len(n),len(n))
        for i,j := 0,1; j < len(n); {
            switch{
                case n[j] == n[i]:
                    table[j] = i + 1
                    i++
                    j++
                case i == 0:
                     j++
                default:
                    i = table[i - 1]
            }
        }
        
        return table
    }
    
    func strStr(haystack string, needle string) int {
        if len(needle) == 0{
            return 0
        }
        
        if len(haystack) == 0{
            return -1
        }
    
        t :=  buildKmp(needle)
        res := -1 
        
        for i,j := 0,0; i <= len(haystack);{
            if j == len(needle){
                res =  i - len(needle)
                break
            }
            
            if i == len(haystack){
                break
            }
            
            if haystack[i] == needle[j] {
                i++
                j++
            }else{
                if j == 0{
                    i++
                }else{
                    j = t[j - 1]
                }
            }
        }
        
        return res
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.