KMP Algorithm in Python


  • 0
    W

    Here attached is my python Solution using KMP Algorithm.
    The main idea is that we use the pattern inside the Pattern String, so that once we encounter a 'miss match', we can skip several bits to shorten the searching range. In Brute-Force algorithm, each time we will just switch to the next bit and start to compare from the very beginning.

    It consists of two parts:

    1. getNext():
      Given a Pattern String "abdyab", we can get next = [-1, 0, 0, 0, 0, 1];
      Let me show you a simple way to get next Array:
      Pattern: "a b d y a b"
      First: "0 0 0 0 1 2"
      SubString that begins from the beginning to 'a' has no match of prefix and suffix, so we get 0;
      Same as 'b' , 'd', y', till 'a'.
      Now you can see the first 'a' (prefix) matches this 'a'(suffix), and the matched length is 1, So we get 1;
      You can go all the way to the end.
      Then, do a little trick: Right shift by one bit and put '-1' on the first element.
      Thus, you got '-1, 0, 0, 0, 0, 1'

    2. Start searching using the principle shown in the main idea.

    Code and have fun:)

    class Solution(object):
        def strStr(self, haystack, needle):
            if not needle:
                return 0
            length_hay = len(haystack)
            length_needle = len(needle)
            next = self.getNext(needle)
            i = 0
            j = 0
            while i < length_hay:
                if j == -1 or needle[j] == haystack[i]:
                    j += 1
                    i += 1
                    if j == length_needle:
                        return i - j
                else:
                    j = next[j]
            return -1
            
        def getNext(self, needle):
            next = []
            next.append(-1)
            length = len(needle)
            j = 0
            k = -1
            while j < length - 1:
                if k == -1 or needle[j] == needle[k]:
                    j += 1
                    k += 1
                    next.append(k)
                else:
                    k = next[k]
            return next
    

Log in to reply
 

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