KMP in Python, but very slow :(


  • 0
    C

    Guys, I tried to wrote the KMP algorithm, but it's very slow. Anyone can do me a favor to figure out where the problem is ? Thanks!

    class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            # Define next array
            def next_arr(needle):
                next = [-1]*len(needle)
                for i in range(1, len(needle)):
                    j = next[i-1]
                    while j>=0 and needle[j+1] != needle[i]:
                        j = next[j]
                    next[i] = j+1 if needle[j+1] == needle[i] else j
                return next
    
            # Find the index of substr
            def sub_str(haystack, needle, next):
                j = -1
                for i in range(-1, len(haystack)-1):
                    while j > -1 and haystack[i+1] != needle[j+1]:
                        j = next[j]
                    j = j+1 if haystack[i+1] == needle[j+1] else j
                    if j == len(needle)-1:
                        return i+1-j
                return -1
                
            if len(needle) > len(haystack):
                return -1
            if not needle:
                return 0
            next = next_arr(needle)
            return sub_str(haystack, needle, next)
            
                        
    

Log in to reply
 

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