KMP via Python


  • 0
    Z

    '''
    def strStr(self, haystack, needle):

        if not needle: return 0
        
     
        j = 0; i = 1;
        lps = [None] * len(needle)
        lps[0] = 0
        
        while i< len(needle):
            if needle[i] == needle[j]:
                lps[i] = j+1
                i += 1
                j += 1
            else: # needle[i] != needle[j]
                if j != 0:
                    j = lps[j-1]
                else: # j == 0
                    lps[i] = 0
                    i += 1
        
    
    
        nIdx = 0; hIdx = 0
       
        while hIdx < len(haystack):
            if needle[nIdx] == haystack[hIdx]:
                nIdx += 1
                hIdx += 1
                if nIdx == len(needle):
                    return hIdx - nIdx
                    
            else:
                if nIdx != 0:
                    nIdx = lps[nIdx -1]
                else:
                    hIdx += 1
                    
        return -1
    

    '''


Log in to reply
 

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