My Python KMP


  • 0
    class Solution(object):
        def strStr(self, haystack, needle):
            def next(s):
                next = [ 0 for i in xrange(len(s) + 1) ]
                for i in xrange(1, len(s)):
                    j = next[i]
                    while j and s[i] != s[j]:
                        j = next[j]
                    next[i + 1] = j + 1 if s[i] == s[j] else 0
                return next
            if not needle:
                return 0
            next = next(needle)
            j = 0
            for i in xrange(len(haystack)):
                while j and haystack[i] != needle[j]:
                    j = next[j]
                j = j + 1 if haystack[i] == needle[j] else 0
                if j == len(needle):
                    return i - j + 1
            return -1
    

Log in to reply
 

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